KIT | KIT-Bibliothek | Impressum | Datenschutz

Fast Succinct Retrieval and Approximate Membership Using Ribbon

Dillinger, Peter C. ; Hübschle-Schneider, Lorenz 1; Sanders, Peter ORCID iD icon 1; Walzer, Stefan
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

A retrieval data structure for a static function f: S → {0,1}^r supports queries that return f(x) for any x ∈ S. Retrieval data structures can be used to implement a static approximate membership query data structure (AMQ), i.e., a Bloom filter alternative, with false positive rate 2^{-r}. The information-theoretic lower bound for both tasks is r|S| bits. While succinct theoretical constructions using (1+o(1))r|S| bits were known, these could not achieve very small overheads in practice because they have an unfavorable space-time tradeoff hidden in the asymptotic costs or because small overheads would only be reached for physically impossible input sizes. With bumped ribbon retrieval (BuRR), we present the first practical succinct retrieval data structure. In an extensive experimental evaluation BuRR achieves space overheads well below 1% while being faster than most previously used retrieval data structures (typically with space overheads at least an order of magnitude larger) and faster than classical Bloom filters (with space overhead ≥ 44%). This efficiency, including favorable constants, stems from a combination of simplicity, word parallelism, and high locality.
... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000149128
Veröffentlicht am 28.07.2022
Originalveröffentlichung
DOI: 10.4230/LIPIcs.SEA.2022.4
Scopus
Zitationen: 6
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-9597725-1-8
ISSN: 1868-8969
KITopen-ID: 1000149128
Erschienen in 20th International Symposium on Experimental Algorithms (SEA 2022). Ed.: C. Schulz
Veranstaltung 20th International Symposium on Experimental Algorithms (SEA 2022), Heidelberg, Deutschland, 25.07.2022 – 27.07.2022
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 4
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 233
Schlagwörter AMQ, Bloom filter, dictionary, linear algebra, randomized algorithm, retrieval data structure, static function data structure, succinct data structure, perfect hashing
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page