论文标题
bloomrf：基于分段 - 单孔哈希函数和二元痕迹树的Bloom过滤器进行射程震荡
bloomRF: On Performing Range-Queries with Bloom-Filters based on Piecewise-Monotone Hash Functions and Dyadic Trace-Trees
论文作者
论文摘要
我们将BloomRF作为一种统一方法，用于近似成员资格测试，该方法支持单个数据结构上的点和范围。 Bloomrf通过范围查询支持扩展了Bloom-Filters，并可能更换它们。核心思想是采用二元间隔方案来确定涵盖数据点的二元间隔集，然后对其进行编码和插入。 Bloomrf将二元痕迹树引入了新的数据结构，该数据结构代表了那些覆盖间隔的新数据结构。 Trace-Tree编码方案在紧凑的位表示中有效地表示覆盖间隔的集合。此外，Bloomrf引入了新型的分段 - 单孔散发函数，这些函数是局部订购的，因此支持范围查询。我们提出了一种用于范围难题的有效的会员计算方法。虽然，BloomRF是为整数设计的，它也支持字符串和浮点数据类型。它还可以处理多个属性并用作多属性过滤器。 我们在RocksDB和独立库中评估Bloomrf。 Bloomrf更有效，在各种设置中，最多优于现有的点范围滤波器4倍。
We introduce bloomRF as a unified method for approximate membership testing that supports both point- and range-queries on a single data structure. bloomRF extends Bloom-Filters with range query support and may replace them. The core idea is to employ a dyadic interval scheme to determine the set of dyadic intervals covering a data point, which are then encoded and inserted. bloomRF introduces Dyadic Trace-Trees as novel data structure that represents those covering intervals implicitly. A Trace-Tree encoding scheme represents the set of covering intervals efficiently, in a compact bit representation. Furthermore, bloomRF introduces novel piecewise-monotone hash functions that are locally order-preserving and thus support range querying. We present an efficient membership computation method for range-queries. Although, bloomRF is designed for integers it also supports string and floating-point data types. It can also handle multiple attributes and serve as multi-attribute filter. We evaluate bloomRF in RocksDB and in a standalone library. bloomRF is more efficient and outperforms existing point-range-filters by up to 4x across a range of settings.
