Informatik
Refine
Document Type
- Conference proceeding (10)
- Book chapter (2)
Has full text
- yes (12)
Is part of the Bibliography
- yes (12)
Institute
- Informatik (12)
Publisher
- Association for Computing Machinery (4)
- Springer (4)
- OpenProceedings (2)
- IEEE (1)
- Universität Konstanz (1)
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.