Name
Title | ||
|---|---|---|
bloomRF: On Performing Range-Queries in Bloom-Filters with Piecewise-Monotone Hash Functions and Prefix Hashing |
Abstract | ||
|---|---|---|
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 piecewise-monotone 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 4x across a range of settings and distributions, while keeping the false-positive rate low. |
Year | DOI | Venue |
|---|---|---|
2023 | 10.48786/EDBT.2023.11 | International Conference on Extending Database Technology (EDBT) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernhard Mößner | 1 | 0 | 0.34 |
| Christian Riegger | 2 | 3 | 3.77 |
| Arthur Bernhardt | 3 | 0 | 1.01 |
| Ilia Petrov | 4 | 83 | 20.20 |