Fixed Block Compression Boosting in FM-Indexes : Theory and Practice

Show full item record



Gog , S , Kärkkäinen , J , Kempa , D , Petri , M & Puglisi , S J 2019 , ' Fixed Block Compression Boosting in FM-Indexes : Theory and Practice ' , Algorithmica , vol. 81 , no. 4 , pp. 1370-1391 .

Title: Fixed Block Compression Boosting in FM-Indexes : Theory and Practice
Author: Gog, Simon; Kärkkäinen, Juha; Kempa, Dominik; Petri, Matthias; Puglisi, Simon J.
Contributor organization: Department of Computer Science
Practical Algorithms and Data Structures on Strings research group / Juha Kärkkäinen
Helsinki Institute for Information Technology
Genome-scale Algorithmics research group / Veli Mäkinen
Algorithmic Bioinformatics
Date: 2019-04
Language: eng
Number of pages: 22
Belongs to series: Algorithmica
ISSN: 0178-4617
Abstract: The FM index (Ferragina and Manzini in J ACM 52(4):552-581, 2005) is a widely-used compressed data structure that stores a string T in a compressed form and also supports fast pattern matching queries. In this paper, we describe new FM-index variants that combine nice theoretical properties, simple implementation and improved practical performance. Our main theoretical result is a new technique called fixed block compression boosting, which is a simpler and faster alternative to optimal compression boosting and implicit compression boosting used in previous FM-indexes. We also describe several new techniques for implementing fixed-block boosting efficiently, including a new, fast, and space-efficient implementation of wavelet trees. Our extensive experiments show the new indexes to be consistently fast and small relative to the state-of-the-art, and thus they make a good off-the-shelf choice for many applications.
Subject: Text indexing
Wavelet tree
Compression boosting
Suffix array
Pattern matching
113 Computer and information sciences
Peer reviewed: Yes
Usage restriction: closedAccess

Files in this item

Total number of downloads: Loading...

Files Size Format View
faster_minuter.pdf 280.7Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record