KIT | KIT-Bibliothek | Impressum | Datenschutz

Engineering Compact Data Structures for Rank and Select Queries on Bit Vectors

Kurpicz, Florian 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

Bit vectors are fundamental building blocks of succinct data structures used in compressed text indices, e.g., in the form of the wavelet trees. Here, two types of queries are of interest: rank and select queries. In practice, the smallest (uncompressed) rank and select data structure cs-poppy has a space overhead of ≈ 3.51 % [Zhou et al. SEA 2013] [26]. Using the same overhead, we present a data structure that can answer queries up to 8 % (rank) and 16.5 % (select) faster compared with cs-poppy.


Verlagsausgabe §
DOI: 10.5445/IR/1000153209
Veröffentlicht am 28.11.2022
Originalveröffentlichung
DOI: 10.1007/978-3-031-20643-6_19
Scopus
Zitationen: 10
Dimensions
Zitationen: 8
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2022
Sprache Englisch
Identifikator ISBN: 978-3-031-20643-6
ISSN: 0302-9743
KITopen-ID: 1000153209
Erschienen in String Processing and Information Retrieval – 29th International Symposium, SPIRE 2022, Concepción, Chile, November 8–10, 2022, Proceedings. Ed.: D. Arroyuelo
Veranstaltung 29th International Symposium on String Processing and Information Retrieval (SPIRE 2022), Concepción, Chile, 08.11.2022 – 10.11.2022
Verlag Springer International Publishing
Seiten 257–272
Serie Lecture Notes in Computer Science ; 13617
Vorab online veröffentlicht am 01.11.2022
Externe Relationen Konferenz
Nachgewiesen in Dimensions
Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page