# Compressing a petabyte of k-mer matrices

Alix Regnier, Pierre Peterlongo

► To cite this version:

Alix Regnier, Pierre Peterlongo. Compressing a petabyte of k-mer matrices. DSB 2026 - Workshop Data Structures in Bioinformatics, Nicola Prezza, Feb 2026, Venise, Italy. hal-05536124

HAL Id: hal-05536124

https://hal.science/hal-05536124v1

Submitted on 4 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Compressing a petabyte of k-mer matrices

Alix Regnier, Pierre Peterlongo

Univ. Rennes, Inria, CNRS, IRISA - UMR 6074, Rennes, F-350

Efficiently querying petabyte-scale genomic data has the potential to revolutionize research in fields like medicine, ecology, and agronomy. The recent kmindex approach [1], which was applied to a complete snapshot of the Sequence Read Archive (SRA), made possible the creation of logan-search.org [2], a powerful search engine. However, the massive size of the index—about one petabyte—presents considerable challenges in terms of maintenance and usability.

The index consists of binary matrices where rows represent datasets, columns represent k-mers (or their hash values), and cell values indicate k-mer presence (0 or 1). In this work, we propose a practical way to compress such matrices through data preprocessing and block compression. The preprocessing consists of swapping original columns with the aim of creating long runs of identical bits. This reduces matrix entropy, thus making them more compressible for general-purpose compressors. We show that a naive TSP heuristic, such as one based on the Nearest-Neighbor, is efficient for performing this task. The block compression consists of splitting matrices into blocks, compressing each block separately using Zstandard, concatenating compressed blocks, and encoding the starting position of blocks using the Elias-Fano succinct data structure [3,4]. The main objective is to achieve sensible compression ratios while minimising the impact on index creation and query times.

The efficiency of the pre-processing depends on the type of original data. Therefore, we also propose a metric that can be used to estimate the potential benefits of this step before any changes are made to the matrix.

We present experimental results for various types of indexed data. In the best cases, block compression reduces the size of the original index by a factor of two, while the pre-processing step achieves an additional 60% compression ratio.

We also present results on the petabyte-sized index of logan-search [2], which enables to estimate the efficiency of our approach on a big index built from extremely diverse sources.

We will discuss some alternative compression methods that could better compress k-mer matrices.
References

[1] Lemane, T., Lezzoche, N., Lecubin, J., Pelletier, E., Lescot, M., Chikhi, R., & Peterlongo, P. (2024). Indexing and real-time user-friendly queries in terabyte-sized complex genomic datasets with kmindex and ORA. _Nature Computational Science_, _4_(2), 104-109.

[2] Rayan Chikhi, Téo Lemane, Raphaël Loll-Krippleber, Mercè Montoliu-Nerin, Brice Raffestin, et al.. Logan: Planetary-Scale Genome Assembly Surveys Life's Diversity. 2025. (hal-05446815)

[3] Fano, R. M. (1971). _On the number of bits required to implement an associative memory_. Massachusetts Institute of Technology, Project MAC.

[4] Elias, Peter. Efficient storage and retrieval by content and address of static files. Journal of the ACM (JACM) 21.2 (1974): 246-260.