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.
Author of HS Reutlingen | Möß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): | ![]() |