Lossless compression of k-mer matrices enabling random row access

Genomic search engines such as Logan-Search index petabytes of sequencing data as large binary matrices, called k -mer matrices, where each row encodes the presence of a k -mer across thousands to millions of genomic samples. Logan-Search contains a petabyte of binary matrices, and storing them is expensive, yet compression must not prevent fast random access to any matrix row at query time.

We present kmcomp , a lossless compression method for k -mer matrices that satisfies these competing requirements. Block compression partitions the matrix into fixed-size row blocks, each compressed independently; block start positions are stored in an Elias-Fano encoded array, enabling O (1) random access to any block. To improve compressibility without introducing additional decompression steps, we introduce the π -compression: a column reordering that groups similar samples together by solving the Traveling Salesman Problem via a nearest-neighbor heuristic. We accelerate this heuristic with a novel variant of the vantage-point tree, the masked vp-tree , which dynamically prunes nearest-neighbor search space.

On three (meta)genomic datasets, kmcomp achieves compression ratios of 1.3 to 5.4; π -compression further improves these to 1.5 to 51.3. Applied to the Logan-Search petabyte-scale index, compression reduces storage by approximately half, and π -compression adds a further 13% gain. Query overhead remains modest: queries of hundreds of nucleotides incur an absolute latency increase of ≈ 100 ms, and highly compressed indexes can match uncompressed query times thanks to reduced disk reads.