The large genomic data sets used by GIGGLE occupy a large amount of disk space. Could we use compression algorithms to reduce disk space utilization without significantly affecting the runtime?

We used the most common library for data compression in C- zlib. We created a wrapper/interface around the zlib functions for improved usability. We applied compression to the data stored in the data file. In addition to the existing data, we stored the uncompressed sizes in the index file. We added a file header/marker for both index and data files. The file header includes information about the compression method, compression level, and an extra flag reserved for future use. Files without headers from previous versions are assumed to be uncompressed and are read accordingly, thus enabling backward compatibility. We used function pointers to dynamically set the compress/uncompress functions, depending on the compression method mentioned in the file header.

Note: The time duration values are approximate as they are affected by other applications running in the background.

The disk space usage was reduced by 70-72%, but the time taken for the search queries increased by 25-50%. We can conclude that fastlz2 is the best candidate. Compared to the uncompressed version, it reduced the space by around 53%, increased the search times by only 24% and 33% respectively. The indexing time was roughly 2.2 times, which is fine for a one-time task.

1. Get the roadmap_sort.tar.gz file using wget https://s3.amazonaws.com/layerlab/giggle/roadmap/roadmap_sort.tar.gz
2. Extract the file using tar -zxvf roadmap_sort.tar.gz
3. Get the GSM1218850_MB135DMMD.peak.q100.bed.gz file using wget https://raw.githubusercontent.com/sspathare97/s22-is-report-giggle/main/GSM1218850_MB135DMMD.peak.q100.bed.gz
4. Install hyperfine, a command-line benchmarking tool.
5. In the disk_store.c file in the GIGGLE repo,
   1. On line 31, update the compression_method (accepted values- 'z' for zlib or 'f' for fastlz)
   2. On line 32, update the compression_level (accepted values- 0 to 9 for zlib and 1 or 2 for fastlz)
6. Build the giggle binary using the make command in the repository. Make sure the variable $GIGGLE_ROOT is set.
7. Make the directories roadmap_sort_comparisons/index, roadmap_sort_comparisons/search1, roadmap_sort_comparisons/search2
8. Run the following set of commands for each combination of compression_method and compression_level. For example, here the name is zlib3 for using zlib with level 3. Replace it with other values.
   1. hyperfine '$GIGGLE_ROOT/bin/giggle index -s -f -i "roadmap_sort/*gz" -o zlib3' --export-csv roadmap_sort_comparisons/index/zlib3.csv -M 1
   2. ls -l zlib3/cache* | awk '{s+=$5;}END{print "zlib3,"s;}' >> roadmap_sort_comparisons/space.csv
   3. hyperfine -w 3 '$GIGGLE_ROOT/bin/giggle search -i zlib3 -q GSM1218850_MB135DMMD.peak.q100.bed.gz' --export-csv roadmap_sort_comparisons/search1/zlib3.csv
   4. hyperfine -w 3 '$GIGGLE_ROOT/bin/giggle search -i zlib3 -r 1:1-1000000' --export-csv roadmap_sort_comparisons/search2/zlib3.csv
9. Analyze the results in the roadmap_sort_comparisons directory.

After compressing the files for leaves, currently, the file that takes up the most space is the offset index file- offset_index.dat. It stores a list of a pair of integers x and y where x is the file ID and y is the line ID in that file. We need the ability to read a particular position in the compressed file. After exploring various ways to implement compression, we concluded that we should implement block impression.

• 0-63 (8B) : num- the number of file_id_offset_pairs stored in the file
• 64-95 (4B) : width- the width of each file_id_offset_pair, currently 96 bits (12B)
  • Each file_id_offset_pair stores the two integers mentioned above
    • 32 bit file_id (x)
    • 64 bit offset (y)
• 96-... : file_id_offset_pairs

In the following diagram, Ryan has explained well how block compression could be implemented for offset_index.dat.

Block Compression- Ryan Layer

1. We will store a fixed number of pairs of integers as one block and then apply the compression on each block. What a good block size could be needs to be determined experimentally.
2. Currently, the leaf node stores I_10- which is the offset_id in the offset_index.dat file. Instead of storing I_10, we will store two values- the compressed block offset ID and the line offset ID within that block.
3. We will also store the compressed offsets for each compressed block.
4. To retrieve the original uncompressed I_10/offset_id, we will seek compressed file to the compressed block offset ID. We will uncompress the whole block and then seek to the line offset ID.

• 0-63 (8B) : num- the number of file_id_offset_pairs stored in the file
• 64-95 (4B) : width- the width of each file_id_offset_pair, currently 96 bits (12B)
• 96-127 (4B) : block_size- the size of each uncompressed block- same for all blocks
• 128-... : compressed_offsets- the offset of each compressed block
• ...-... : compressed_data- the actual compressed blocks

We will create a standalone program called block_compression.c with the following functionality-

1. Compress offset_index.dat to offset_index_compressed.dat
2. Uncompress offset_index_compressed.dat to offset_index.dat
3. Read offset_id from offset_index.dat
4. Read offset_id from offset_index_compressed.dat

We need to write unit tests to make sure the output from 3 and 4 are the same.

• mmap usage
• offset_data_append_data function pointer usage instead of fwrite
• OFFSET_INDEX_DATA macro definition

• Figure out how to store two values in the leaf store

• Added data files and executable files in the unit tests to gitignore.
• Fixed the unit tests Makefile issue that prevented two consecutive builds without running make clean- the _Runner.c files were also being considered for tests. Added wildcard filter to ignore them.
• Fixed minor bugs and formatting.