SNARF: A Learning-Enhanced Range Filter
SNARF: A Learning-Enhanced Range Filter
复制标题
DOI：
10.14778/3529337.3529347
复制
发表时间：
2022-04
期刊：
影响因子：
--
通讯作者：
Kapil Vaidya;Tim Kraska;Subarna Chatterjee;Eric R. Knorr;M. Mitzenmacher;Stratos Idreos
中科院分区：
文献类型：
--
作者：
Kapil Vaidya;Tim Kraska;Subarna Chatterjee;Eric R. Knorr;M. Mitzenmacher;Stratos Idreos
我们提出了基于稀疏数值数组的范围过滤器（SNARF），一个学习的范围过滤器，有效地支持数值数据的范围查询。SNARF创建数据分布模型，将键映射到以压缩形式存储的位数组中。该模型与构成SNARF的压缩位数组一起沿着用于回答成员资格查询。我们评估SNARF在多个合成和真实世界的数据集作为一个独立的过滤器，并将其集成到RocksDB。对于范围查询，SNARF提供了高达50倍的误报率比最先进的范围过滤器，如SuRF和Rosetta，具有相同的空间使用。我们还评估了RocksDB中的SNARF作为过滤器的替代品，用于在访问磁盘上的数据结构之前过滤请求。对于RocksDB，对于某些只读工作负载，SNARF可以将系统的执行时间提高到SuRF和Rosetta的10倍。
We present Sparse Numerical Array-Based Range Filters (SNARF), a learned range filter that efficiently supports range queries for numerical data. SNARF creates a model of the data distribution to map the keys into a bit array which is stored in a compressed form. The model along with the compressed bit array which constitutes SNARF are used to answer membership queries. We evaluate SNARF on multiple synthetic and real-world datasets as a stand-alone filter and by integrating it into RocksDB. For range queries, SNARF provides up to 50x better false positive rate than state-of-the-art range filters, such as SuRF and Rosetta, with the same space usage. We also evaluate SNARF in RocksDB as a filter replacement for filtering requests before they access on-disk data structures. For RocksDB, SNARF can improve the execution time of the system up to 10x compared to SuRF and Rosetta for certain read-only workloads.