A Practical Alphabet-Partitioning Rank/Select Data Structure

Diego Arroyuelo, Erick Sepúlveda

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferencia

Resumen

© 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.
Idioma originalInglés
Título de la publicación alojadaA Practical Alphabet-Partitioning Rank/Select Data Structure
Páginas452-466
Número de páginas15
ISBN (versión digital)9783030326852
DOI
EstadoPublicada - 1 ene 2019
EventoLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) -
Duración: 1 ene 2019 → …

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen11811 LNCS
ISSN (versión impresa)0302-9743

Conferencia

ConferenciaLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Período1/01/19 → …

Huella Profundice en los temas de investigación de 'A Practical Alphabet-Partitioning Rank/Select Data Structure'. En conjunto forman una huella única.

  • Citar esto

    Arroyuelo, D., & Sepúlveda, E. (2019). A Practical Alphabet-Partitioning Rank/Select Data Structure. En 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