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

Share in Twitter Search Google Scholar


Author of HS ReutlingenMößner, Bernhard; Riegger, Christian; Bernhardt, Arthur; Petrov, Ilia
Publisher:Open Proceedings.org, Univ. of Konstanz
Place of publication:Konstanz
Document Type:Conference proceeding
Publication year:2023
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