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): |  Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International |
