Succinct range filters

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

Publication Type: Journal article

Publication year: 2021

Journal

Communications of the ACM ACM Association for Computing Machinery

Book Volume: 64

Pages Range: 166-173

Journal Issue: 4

DOI: 10.1145/3450262

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, such as range counts. SuRF is based on a new data structure called the Fast Succinct Trie (FST) that matches the performance of state-of-the-art order-preserving indexes, while consuming only 10 bits per trie node - -a space close to the minimum required by information theory. Our experiments show that SuRF speeds up range queries in a widely used database storage engine by up to 5×.

Authors with CRIS profile

Viktor Leis

Involved external institutions

Carnegie Mellon University US United States (USA) (US) Hewlett-Packard Company US United States (USA) (US) Friedrich-Schiller-Universität Jena DE Germany (DE)

How to cite

APA:

Zhang, H., Lim, H., Leis, V., Andersen, D.G., Kaminsky, M., Keeton, K., & Pavlo, A. (2021). Succinct range filters. Communications of the ACM, 64(4), 166-173. https://dx.doi.org/10.1145/3450262

MLA:

Zhang, Huanchen, et al. "Succinct range filters." Communications of the ACM 64.4 (2021): 166-173.

BibTeX: Download