KIT | KIT-Bibliothek | Impressum | Datenschutz

Concurrent Expandable AMQs on the Basis of Quotient Filters

Maier, Tobias; Sanders, Peter; Williger, Robert

Abstract:
A quotient filter is a cache efficient Approximate Membership Query (AMQ) data structure. Depending on the fill degree of the filter most insertions and queries only need to access one or two consecutive cache lines. This makes quotient filters very fast compared to the more commonly used Bloom filters that incur multiple independent memory accesses depending on the false positive rate. However, concurrent Bloom filters are easy to implement and can be implemented lock-free while concurrent quotient filters are not as simple. Usually concurrent quotient filters work by using an external array of locks - each protecting a region of the table. Accessing this array incurs one additional memory access per operation. We propose a new locking scheme that has no memory overhead. Using this new locking scheme we achieve 1.6× times higher insertion performance and over 2.1× higher query performance than with the common external locking scheme. Another advantage of quotient filters over Bloom filters is that a quotient filter can change its capacity when it is becoming full. We implement this growing technique for our concurrent quotient filters and adapt it in a way that allows unbounded growing while keeping a bounded false positive rate. ... mehr

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000125844
Veröffentlicht am 09.11.2020
Originalveröffentlichung
DOI: 10.4230/LIPIcs.SEA.2020.15
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsdatum 12.06.2020
Sprache Englisch
Identifikator ISBN: 978-3-9597714-8-1
ISSN: 1868-8969
KITopen-ID: 1000125844
Erschienen in 18th International Symposium on Experimental Algorithms : SEA 2020, June 16-18, 2020, Catania, Italy / edited by Simone Faro, Domenico Cantone
Veranstaltung 18th International Symposium on Experimental Algorithms (SEA 2020), Online, 16.06.2020 – 18.06.2020
Verlag Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Saarbrücken/Wadern
Seiten 15:1–15:13
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 160
Bemerkung zur Veröffentlichung Die Veranstaltung fand wegen der Corona-Pandemie als Online-Event statt.
Externe Relationen Siehe auch
Abstract/Volltext
Schlagwörter Quotient filter, concurrent data-structures, approximate membership query, fingerprints
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page