Diva - Dynamic Range Filter for Var-Length Keys and Queries

Aug 26, 2026

Range filters are compact probabilistic data structures that estimate whether a key range is empty, enabling fast elimination of non-matching lookups in systems like key-value stores. Existing solutions fall short in multiple ways: they lack strong false-positive rate and performance guarantees, they cannot handle variable-length keys and query ranges, and they do not support dynamic updates. Diva simultaneously addresses these issues using a cache-efficient trie, infix compression, and dynamic blocks for insertions, deletions, and expansions, achieving competitive false-positive rates with robust theoretical and empirical results.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages14

Reading Time35 min

AccessFree to download

Abstract

Introduction

What is a Filter?

Range Filters and Applications

Range Filtering Goals

Design Contentions

Core Contribution: Diva

Diva: Dynamic Range Filter for Var-Length Keys and Queries Navid Eslami [navideslami@cs.toronto.edu](navideslami@cs.toronto.edu)[ ](navideslami@cs.toronto.edu)University of Toronto Toronto, Canada Ioana O. Bercea [bercea@kth.se](bercea@kth.se) KTH Royal Institute of Technology Stockholm, Sweden Niv Dayan [nivdayan@cs.toronto.edu](nivdayan@cs.toronto.edu)[ ](nivdayan@cs.toronto.edu)University of Toronto Toronto, Canada ABSTRACT Range filters are compact probabilistic 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 oneof 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 cache-efficient 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 splits to handle insertions and expansions. It processes a range query by traversing the trie and checking for the inclusion of infixes in the target query range. We show, theoretically and empirically, that Diva achieves a false positive rate on par with the state of the art on real-world datasets while supporting dynamicity and variable-length queries and keys. PVLDB Reference Format: Navid Eslami, Ioana O. Bercea, and Niv Dayan. Diva: Dynamic Range Filter for Var-Length Keys and Queries. PVLDB, 18(11): 3923-3936, 2025 . doi:10.14778/3749646.3749664 PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at [https://github.com/n3slami/Diva.git](https://github.com/n3slami/Diva.git). 1 INTRODUCTION What is a Filter? A filter is a memory-efficient probabilistic data structure that answers whether a query key exists in a given set. Its compactness allows it to fit in a higher level of the memory hierarchy than the set it represents, making it fast to query. A filter never returns a false negative but may return a false positive with a probability called the False Positive Rate (FPR) that depends on its memory footprint. Due to these qualities, filters are used in many applications to avoid redundant disk reads [21] and network hops [10] when a query happens to target a nonexistent key. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit [https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of](https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of)[ ](https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of)[this license. For any use beyond those covered by this license](this license. For any use beyond those covered by this license), [obtain permission by](obtain permission by)[emailing info@vldb.org. Copyright](emailing info@vldb.org. Copyright) is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 18, No. 11 ISSN 2150-8097 . doi:10.14778/3749646.3749664 Range Filters and Applications. Traditional filters answer membership queries for a single key. In contrast, a range filter accepts two keys as the end-points of a range and determines if at least one key in the set is in-between them. As with a traditional filter, a range filter does not return false negatives but may return false positives. Range filters are

FAQs

What problem does a range filter solve in key-value and storage systems?

A range filter determines whether any stored key falls within a query interval. It avoids unnecessary disk reads or network hops when the target range cannot contain matching keys, while guaranteeing no false negatives.

What limitations affect existing range filters according to the document?

Existing range filters lack robust false-positive rate and performance guarantees, cannot support variable-length keys and query ranges, and generally do not allow dynamic operations like insertions, deletions, or expansions.

How does Diva enable dynamic operations and variable-length keys/queries?

Diva learns the dataset distribution by sampling keys into a cache-efficient trie, compresses keys between samples using infix-based representations, and stores infixes in constant-time dynamic data blocks that can be split to support insertions and expansions. It answers range queries by traversing the trie and checking infix inclusion in the target range.

Aug 26, 2026

Uploaded by Caleb Sterling