A bloated FM-index reducing the number of cache misses during the search

preprint2015arXivOpen access

Abstract

The FM-index is a well-known compressed full-text index, based on the Burrows-Wheeler transform (BWT). During a pattern search, the BWT sequence is accessed at "random" locations, which is cache-unfriendly. In this paper, we are interested in speeding up the FM-index by working on qq-grams rather than individual characters, at the cost of using more space. The first presented variant is related to an inverted index on qq-grams, yet the occurrence lists in our solution are in the sorted suffix order rather than text order in a traditional inverted index. This variant obtains O(m/∣CL∣+log⁡nlog⁡m)O(m/|CL| + \log n \log m) cache misses in the worst case, where nn and mm are the text and pattern lengths, respectively, and ∣CL∣|CL| is the CPU cache line size, in symbols (typically 64 in modern hardware). This index is often several times faster than the fastest known FM-indexes (especially for long patterns), yet the space requirements are enormous, O(nlog⁡2n)O(n\log^2 n) bits in theory and about 80n80n-95n95n bytes in practice. For this reason, we dub our approach FM-bloated. The second presented variant requires O(nlog⁡n)O(n\log n) bits of space.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.