TY  - CHAP
U1  - Konferenzveröffentlichung
A1  - Mößner, Bernhard
A1  - Riegger, Christian
A1  - Bernhardt, Arthur
A1  - Petrov, Ilia
T1  - bloomRF: On performing range-queries in Bloom-Filters with piecewise-monotone hash functions and prefix hashing
T2  - Advances in database technology : Proceedings of the 26th International Conference on Extending database Technology (EDBT), 28th March - 31st March 2023, Ioannina, Greece
N2  - 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.
Y1  - 2023
UN  - https://nbn-resolving.org/urn:nbn:de:bsz:rt2-opus4-41604
SN  - 978-3-89318-088-2
SB  - 978-3-89318-088-2
U6  - https://doi.org/10.48786/edbt.2023.11
DO  - https://doi.org/10.48786/edbt.2023.11
VL  - 26
SP  - 131
EP  - 143
S1  - 13
PB  - OpenProceedings
CY  - Konstanz
ER  -