Volltext-Downloads (blau) und Frontdoor-Views (grau)

bloomRF: On performing range-queries in Bloom-Filters with piecewise-monotone hash functions and prefix hashing

  • We introduce bloomRF as a unified method for approximate membership testing that supports both point- and range-queries. As a first core idea, bloomRF introduces novel prefix hashing to efficiently encode range information in the hash-code of the key itself. As a second key concept, bloomRF proposes novel piecewisemonotone hash-functions that preserve local order and support fast range-lookups with fewer memory accesses. bloomRF has near-optimal space complexity and constant query complexity. Although, bloomRF is designed for integer domains, it supports floating-points, and can serve as a multi-attribute filter. The evaluation in RocksDB and in a standalone library shows that it is more efficient and outperforms existing point-range-filters by up to 4× across a range of settings and distributions, while keeping the false-positive rate low.

Download full text files

Export metadata

Additional Services

Search Google Scholar

Statistics

frontdoor_oas
Metadaten
Author of HS ReutlingenMößner, Bernhard; Riegger, Christian; Bernhardt, Arthur; Petrov, Ilia
URN:urn:nbn:de:bsz:rt2-opus4-41604
DOI:https://doi.org/10.48786/edbt.2023.11
ISBN:978-3-89318-088-2
Publisher:Open Proceedings.org, Univ. of Konstanz
Place of publication:Konstanz
Document Type:Conference proceeding
Language:German
Publication year:2023
Volume:26
Page Number:13
First Page:131
Last Page:143
DDC classes:004 Informatik
Open access?:Ja
Licence (German):License Logo  Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International