A Practical Alphabet-Partitioning Rank/Select Data Structure

Diego Arroyuelo, Erick Sepúlveda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

© 2019, Springer Nature Switzerland AG. This paper proposes a practical implementation of an alphabet-partitioning compressed data structure, which represents a string within compressed space and supports the fundamental operations and efficiently. We show experimental results that indicate that our implementation outperforms the current realizations of the alphabet-partitioning approach (which is one of the most efficient approaches in practice). In particular, the time for operation can be reduced by about 80%, using only 11% more space than current alphabet-partitioning schemes. We also show the impact of our data structure on several applications, like the intersection of inverted lists (where improvements of up to 60% are achieved, using only 2% of extra space), and the distributed-computation processing of and operations. As far as we know, this is the first study about the support of operations on a distributed-computing environment.
Original languageEnglish
Title of host publicationA Practical Alphabet-Partitioning Rank/Select Data Structure
Pages452-466
Number of pages15
ISBN (Electronic)9783030326852
DOIs
Publication statusPublished - 1 Jan 2019
EventLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) -
Duration: 1 Jan 2019 → …

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11811 LNCS
ISSN (Print)0302-9743

Conference

ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Period1/01/19 → …

Fingerprint Dive into the research topics of 'A Practical Alphabet-Partitioning Rank/Select Data Structure'. Together they form a unique fingerprint.

  • Cite this

    Arroyuelo, D., & Sepúlveda, E. (2019). A Practical Alphabet-Partitioning Rank/Select Data Structure. In A Practical Alphabet-Partitioning Rank/Select Data Structure (pp. 452-466). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11811 LNCS). https://doi.org/10.1007/978-3-030-32686-9_32