EUVIMEDEUVIMED entdecken
Crossref

Dynamic Range Filtering Beyond Worst-Case Bounds

Navid Eslami, Ioana O. Bercea, Niv Dayan

ACM SIGMOD Record · 23.04.2026 · 55 (1) · 51-60

DOI: 10.1145/3810900.3810910 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM SIGMOD Record, online erschienen am 23.04.2026. Verfasst von Navid Eslami und 2 weiteren Autor:innen. Die Arbeit nennt 59 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Range filters are compact data structures that answer approximate range emptiness queries. They are used in many domains, e.g., in key-value stores, to quickly rule out the existence of keys in a given query range and avoid having to search for them in storage. However, all existing range filters exhibit at least one of the following shortcomings: (1) they do not provide robust false positive rate and performance guarantees, (2) they do not support variable-length keys and query ranges, and (3) they do not allow dynamic operations such as insertions, deletions, or expansions. We introduce Diva, the first range filter to address all the above challenges simultaneously. Diva learns the dataset's distribution by sampling keys and storing them in a cacheefficient trie. It compresses the keys in-between samples by removing their longest common prefix and truncating their suffixes while leaving enough bits in the middle (i.e., an infix) to allow differentiating between the keys in the sorted order. It stores infixes in constant-time dynamic data blocks, which it stretches and eventually splits to handle insertions and expansions. It processes a range query by traversing the trie and checking for the inclusion of at least one infix in the target query range. Diva is the culmination of several years of research on filters from Orca Lab at the University of Toronto, in collaboration with KTH and Copenhagen University. This paper describes how Diva builds on this body of work, and how it addresses the limitations of prior art.

Zitieren

APA

Eslami, N., Bercea, I. O., & Dayan, N. (2026). Dynamic Range Filtering Beyond Worst-Case Bounds. ACM SIGMOD Record, 55(1), 51-60. https://doi.org/10.1145/3810900.3810910

Vancouver

Eslami N, Bercea IO, Dayan N. Dynamic Range Filtering Beyond Worst-Case Bounds. ACM SIGMOD Record. 2026;55(1):51-60. doi:10.1145/3810900.3810910

BibTeX
@article{Eslami2026,
  author = {Eslami, Navid and Bercea, Ioana O. and Dayan, Niv},
  title = {Dynamic Range Filtering Beyond Worst-Case Bounds},
  journal = {ACM SIGMOD Record},
  year = {2026},
  volume = {55},
  number = {1},
  pages = {51--60},
  doi = {10.1145/3810900.3810910}
}
Kostenlos starten →