SuRF: Practical range query filtering with fast succinct tries

Zhang H, Lim H, Leis V, Andersen DG, Kaminsky M, Keeton K, Pavlo A (2018)

Publication Type: Conference contribution

Publication year: 2018

Publisher: Association for Computing Machinery

Pages Range: 323-336

Conference Proceedings Title: Proceedings of the ACM SIGMOD International Conference on Management of Data

Event location: Houston, TX US

ISBN: 9781450317436

DOI: 10.1145/3183713.3196931

Abstract

We present the Succinct Range Filter (SuRF), a fast and compact data structure for approximate membership tests. Unlike traditional Bloom filters, SuRF supports both single-key lookups and common range queries: open-range queries, closed-range queries, and range counts. SuRF is based on a newdata structure called the Fast Succinct Trie (FST) that matches the point and range query performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node. The false positive rates in SuRF for both point and range queries are tunable to satisfy different application needs. We evaluate SuRF in RocksDB as a replacement for its Bloom filters to reduce I/O by filtering requests before they access on-disk data structures. Our experiments on a 100 GB dataset showthat replacing RocksDB's Bloom filters with SuRFs speeds up open-seek (without upper-bound) and closed-seek (with upper-bound) queries by up to 1.5× and 5× with a modest cost on the worst-case (all-missing) point query throughput due to slightly higher false positive rate.

Authors with CRIS profile

Viktor Leis

Involved external institutions

Hewlett Packard Enterprise Company (HPE) US United States (USA) (US) Carnegie Mellon University US United States (USA) (US) Intel Corporation US United States (USA) (US) Technische Universität München (TUM) DE Germany (DE)

How to cite

APA:

Zhang, H., Lim, H., Leis, V., Andersen, D.G., Kaminsky, M., Keeton, K., & Pavlo, A. (2018). SuRF: Practical range query filtering with fast succinct tries. In Gautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein (Eds.), Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 323-336). Houston, TX, US: Association for Computing Machinery.

MLA:

Zhang, Huanchen, et al. "SuRF: Practical range query filtering with fast succinct tries." Proceedings of the 44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018, Houston, TX Ed. Gautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein, Association for Computing Machinery, 2018. 323-336.

BibTeX: Download