Sorry, you need to enable JavaScript to visit this website.

On Elias-Fano for Rank Queries in FM-indexes

Primary tabs

Citation Author(s):
Danyang Ma, Simon J. Puglisi, Rajeev Raman, Bella Zhukova
Submitted by:
Bella Zhukova
Last updated:
2 March 2021 - 2:37pm
Document Type:
Presentation Slides
Document Year:
Presenters Name:
Bella Zhukova



We describe methods to support fast rank queries on the Burrows-Wheeler transform (BWT) string S of an input string T on alphabet Σ, in order to support pattern counting queries. Our starting point is an approach previously adopted by several authors, which is to represent S as |Σ| bitvectors, where the bitvector for symbol c has a 1 at position i if and only if S[i] = c, with the bitvec- tors stored in Elias-Fano (EF) encodings, to enable binary rank queries. We first show that the clustering of symbols induced by the BWT makes standard implementations of EF unattractive. We then engineer several improvements to EF that go some way to alleviating this problem, and go on to describe two new EF-inspired bitvectors that have superior practical performance.

0 users have voted:

Dataset Files

presentation slides