Optimized succinct data structures for massive data. (23rd May 2013)

• Record Type: Journal Article
• Authors: Gog, Simon; Petri, Matthias
• Is Part Of: Software, practice & experience. Volume 44:Number 11(2014)
• Page Start: 1287
• Page End: 1314
• Publication Date: 2013-05-23
• Subjects: Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2198
• Languages: English
• ISSNs: 0038-0644

Abstract

<abstract abstract-type="main" id="spe2198-abs-0001"> <title>SUMMARY</title> <p id="spe2198-para-0001">Succinct data structures provide the same functionality as their corresponding traditional data structure in compact space. We improve on functions <italic>rank</italic> and <italic>select</italic>, which are the basic building blocks of FM‐indexes and other succinct data structures. First, we present a cache‐optimal, uncompressed bitvector representation that outperforms all existing approaches. Next, we improve, in both space and time, on a recent result by Navarro and Providel on compressed bitvectors. Last, we show techniques to perform <italic>rank</italic> and <italic>select</italic> on 64‐bit words that are up to three times faster than existing methods. In our experimental evaluation, we first show how our improvements affect cache and runtime performance of both operations on data sets larger than commonly used in the evaluation of succinct data structures. Our experiments show that our improvements to these basic operations significantly improve the runtime performance and compression effectiveness of FM‐indexes on small and large data sets. To our knowledge, our improvements result in FM‐indexes that are either smaller or faster than all current state of the art implementations. Copyright © 2013 John Wiley &amp; Sons, Ltd.</p> </abstract>