New Data Structure Slashes Memory Overhead for Genomic Index Rank Queries

In a study published in Algorithms for Molecular Biology, Simon Gene Gottlieb and Knut Reinert describe three implementation advances that together reduce the memory overhead of rank support structures to as little as 1.6 percent of the underlying data and, for strings over larger alphabets, deliver rank operations that are competitive in size with wavelet trees and between two and nine times faster, depending on the parameters.

The rank operation sits at the heart of the FM-Index, a compressed index widely used to align sequencing reads against reference genomes. The index is built over the Burrows-Wheeler Transform of a text, and at its core it repeatedly asks a deceptively simple question: given a position in the transformed string and a character, how many times does that character appear from the start of the string up to that position? Because a single FM-Index search can issue enormous numbers of such queries, the efficiency of rank support largely determines both the memory footprint and the execution time of the whole index.

In practice, rank queries on strings are usually answered through bit vectors, binary arrays in which each position records whether a particular character occurs there. To answer a rank question in constant time, the bit vector carries auxiliary data: the bits are grouped into blocks and superblocks, and each group stores a prefix sum counting the number of 1 bits in all preceding groups. This binary case has been studied for decades, going back to Jacobson’s demonstration that constant-time queries are possible with sublinear auxiliary memory. Vigna’s 2008 rank9 structure interleaved these layers to cut cache misses at a cost of 25 percent extra space, and Zhou and colleagues reduced that overhead to 3.125 percent in 2013 using 512-bit blocks, an approach Kurpicz refined for cache efficiency in 2022.

The first new contribution, called paired-blocks, attacks that overhead directly. Instead of storing a prefix sum for every block, the method pairs blocks into left and right halves and stores a single value per pair, halving the number of stored entries. When a query lands inside a right block, the stored prefix sum is used as usual. When it lands inside a left block, the stored value overcounts, so the algorithm counts the unwanted trailing bits with a popcount instruction and subtracts them instead. Extended to two layers, the scheme requires postfix sums for left superblocks and a case distinction over left and right positions, but it preserves the same halving principle. The result is a bit vector whose support structure needs only 1.6 percent extra space, roughly half the 3.1 to 3.2 percent required by the previous best implementations.

The second contribution concerns how unwanted bits are cleared before counting. The conventional shift-and-count approach shifts a machine word right so that only the leading bits remain, then applies the hardware popcount instruction. For the paired layout this forces a branch to decide between left and right shifts, and for 512-bit blocks it runs into a hardware gap: the AVX512 SIMD extension offers no shift instruction for full 512-bit words, so the compiler emulates shifts with multiple 64-bit operations and fails to use the wide popcount. The authors’ mask-and-count alternative replaces shifting with a precomputed array of bit masks, indexed by the query position within a pair of blocks, producing branch-free code. In benchmarks on an AMD EPYC 9454 processor compiled with clang 20.0.0, masking made little difference for 64-bit blocks but improved 512-bit rank performance by at least 25 percent and up to 125 percent on the largest 256-megabyte test case.

The third contribution, flattened bit vectors, addresses rank on strings over larger alphabets. The naive multiple-bit-vector solution stores one bit vector per alphabet character, which is fast but consumes space proportional to the text length times the alphabet size. Wavelet trees reduce this to space proportional to the text length times the logarithm of the alphabet size, but each query traverses a tree of depth equal to that logarithm. The EPR-dictionary of Pockrandt and colleagues packs the string itself into a compact representation, but its auxiliary structures grow accordingly and require extra bit extraction operations. Flattened bit vectors instead scatter the bits of each character code across several machine words, reconstructing the bit vector for any queried character with parallel bitwise AND operations, some of them on inverted words. Because the scattered words span full machine words regardless of alphabet size, block and superblock overhead stays low, and the logarithmic number of bit operations executes in parallel on modern hardware.

The benchmark suite used texts of one billion random characters with alphabet sizes of 4, 5, 16, 21 and 255 characters, comparing the new structures against SDSL implementations of wavelet trees and EPR-dictionaries, an adjusted version of Anderson and Wheeler’s AwFmIndex, and a custom multiple-bit-vector reference. For a four-letter DNA-like alphabet, flattened bit vectors cut memory from 4 bits per character with EPR-dictionaries to 3 bits, and the paired 512-bit variant reached 2.065 to 2.129 bits per character, about 20 percent below the wavelet tree. For a 16-character alphabet, EPR-dictionaries became uncompetitive even against the naive multiple-bit-vector approach, while the 512-bit flattened bit vectors were 10 to 15 percent smaller than wavelet trees and more than six times faster.

The largest alphabets revealed the clearest trade-offs. With 255 characters, wavelet trees needed only 10 bits per character, while flattened bit vectors with paired blocks used 25 percent more memory but answered rank queries more than nine times faster. The paired layout itself saved 25 percent memory over the non-paired version at 512-bit blocks and 45 percent at 64-bit blocks, with 512-bit blocks running about 48 percent slower but using roughly 75 percent less support space. The authors note that the study focused on rank rather than select operations, since rank is the operation their group’s FM-Index work requires, and that their benchmarks measured average query time at random positions using the nanobench microbenchmark library on randomly generated rather than real biological texts.

The practical guidance that follows from the measurements is differentiated. For binary alphabets, the authors recommend their 512-bit, 64-kilobit-superblock bit vectors, noting that the extra saving from paired blocks is unlikely to matter at that scale. When speed is the only concern for strings, a multiple-bit-vector implementation remains fastest if memory is no object. For small non-binary alphabets under memory pressure they recommend unpaired flattened bit vectors, and for larger alphabets in all but the most memory-constrained cases they recommend the paired 512-bit variant, which combines a modest space penalty over wavelet trees with speed improvements of up to a factor of nine. Because compressed bit-vector approaches were excluded from the comparison due to their dependence on bit-vector compressibility, and because the benchmarks used synthetic texts, the reported advantages are specific to the tested setting, but the underlying structures are general and work for arbitrary alphabet sizes.

Subject of Research: Engineering faster and more space-efficient rank queries on bit vectors and strings for genomic indexing

Article Title: Engineering rank queries on bit vectors and strings

Article References: Gottlieb, S. G., & Reinert, K. (2025). Engineering rank queries on bit vectors and strings. Algorithms for Molecular Biology, 20(1), Article 21. https://doi.org/10.1186/s13015-025-00291-9

Image Credits: AI Generated

DOI: 10.1186/s13015-025-00291-9

Keywords: rank queries, bit vectors, FM-Index, Burrows-Wheeler Transform, bioinformatics, data structures, genomics, wavelet trees, popcount, AVX512, space efficiency, algorithm engineering