One-sentence Summary

University of Toronto and KTH Royal Institute of Technology propose Diva, the first range filter that simultaneously supports variable-length keys and query ranges, dynamic insertions, deletions, and expansions, and robust false positive rate guarantees by learning the dataset distribution through a cache-efficient trie with infix-based key compression stored in constant-time dynamic data blocks.

Key Contributions

• The paper introduces Diva, the first range filter that simultaneously supports dynamic insertions, deletions, and expansions, variable-length keys and query ranges, and robust false positive rate and performance guarantees.

• The design samples keys into a cache-efficient trie, compresses keys between samples into infixes by removing longest common prefixes and truncating suffixes, and stores those infixes in constant-time dynamic data blocks that split to absorb insertions and expansions.

• Theoretical and empirical evaluation on real-world datasets shows that Diva achieves a false positive rate on par with the state of the art while retaining dynamic updates, variable-length query support, faster predecessor searches, and strong construction speed.

Introduction

Filters are compact probabilistic data structures that avoid needless disk reads and network hops, and range filters extend this idea by skipping data segments that cannot match a range predicate, which matters in systems such as LSM trees, SQL tables, B tree indexes, and distributed key value stores. Prior range filters must trade off key properties: robust designs limit false positives only for bounded query lengths and struggle with variable length keys under tight memory budgets, while learned approaches support flexible queries but often lack efficient updates, variable length key handling, or fast lookup and construction. The authors leverage a cache efficient trie learned from sampled keys, fixed length infix discretization, and ordered infix stores to build Diva, the first range filter that simultaneously supports low false positive rates, arbitrary range queries, variable length keys, dynamic updates, fast queries, and fast construction.

Method

Diva is designed as a range filter whose core architecture separates a learned coarse description of the key distribution from compact interval-local storage for all non-sampled keys. The authors treat the sorted key set as a distribution model: every $T$T-th key is retained as a sample in a trie, while the keys falling between two adjacent samples are represented only through a specialized structure called an Infix Store. As shown in the framework diagram:

The trie provides a predecessor and successor for each region of the key space. The interval between two consecutive samples is managed by one Infix Store. If two samples are close, many keys usually lie between them, so the corresponding Infix Store represents a dense region. If two samples are far apart, fewer keys usually lie between them, so the corresponding Infix Store represents a sparse region. In this way, the trie learns the shape of the distribution. The sample spacing $T$T controls the tradeoff between resolution and memory. Smaller $T$T yields a denser sample set and a finer distribution model, while larger $T$T reduces memory. The implementation uses $T = 1024$T=1024 to obtain strong accuracy with low overhead.

A query is processed first at the trie level. If a range query contains at least one sample key, the filter immediately returns a positive because that sample is an actual key inside the queried interval. If the range does not contain a sample, its endpoints fall between the same pair of adjacent samples, so Diva queries only the associated Infix Store. Point queries are a special case of range queries with equal endpoints.

For every interval between a predecessor sample and a successor sample, Diva encodes the intervening keys as infixes. Keys between the same sample pair share a common leading structure that can be inferred from the trie, so the longest common prefix is removed. Variable-length keys are handled by truncating suffixes while retaining enough middle bits to distinguish keys and meet a target false positive rate $\epsilon$ϵ. Refer to the truncation diagram below:

The retained middle bit sequence is called an infix. If the longest common prefix of the predecessor and successor has length $m_{\mathrm{shared}}^i$msharedi​, Diva removes those prefix bits from each key in the interval. It then selects an infix length

so that the discretized interval contains enough infix values to control the false positive probability. The use of fixed-length infixes removes variation in key length and allows range inclusion checks using integer arithmetic.

Diva also handles a subtlety that arises when the predecessor and successor remain close after removing their longest common prefix. In that case, long runs of matching ones in the predecessor and zeros in the successor do not add useful differentiation. These bits are called redundant bits, and their length is denoted by $m_{\mathrm{redundant}}^i$mredundanti​. Diva removes them and forms each infix from the first differentiating bit concatenated with the first $m_{\mathrm{infix}} - 1$minfix​−1 useful bits that follow. This keeps the valid infix domain large enough, giving between $\frac{T}{\epsilon}$ϵT​ and $\frac{2T}{\epsilon}$ϵ2T​ possible infix values for the interval. The false positive behavior can then be understood by partitioning each Infix Store interval into equal-width subranges, where each subrange corresponds to one infix. Refer to the distribution partitioning illustration:

The probability of a false positive is tied to the probability that a non-member query and a stored key map to the same infix in the same Infix Store. For well behaved distributions, the cumulative distribution function does not change too abruptly inside these small subranges, so each infix captures only a small amount of probability mass. This enables Diva to guarantee a low false positive rate while using a compact per-interval representation.

Each Infix Store stores infixes using quotienting. An infix is split into a remainder made of its least significant bits and a quotient made of the remaining bits. The number of remainder bits is

The store maintains an occupieds bitmap that records which quotients are present. It also maintains an array of slots that stores remainders belonging to each quotient. Remainders with the same quotient are stored in a contiguous group called a run, and the runends bitmap marks the final slot of each run. Runs are stored in increasing quotient order. Because each occupied quotient corresponds to exactly one run, Diva can locate the run for a quotient by using rank and select operations on the two bitmaps. The location of the last slot in the run is computed as

Since infixes in well behaved regions are approximately uniformly distributed, runs are short in expectation. This makes the remainder scan cheap.

For a range query, Diva derives endpoint infixes and compares their quotients and remainders. If the endpoints map to the same quotient, the filter scans the corresponding run from its end backward and checks whether any remainder lies between the endpoint remainders. If the endpoints span multiple quotients, Diva first checks whether any strictly interior quotient is present in the occupieds bitmap. If such a quotient exists, the query must contain all remainders in its run and therefore returns a positive. Otherwise, Diva scans only the endpoint runs and compares remainders against the left and right query remainders.

For construction, the static version assumes sorted input, which is common for column stores, B-Trees, and LSM-Tree based systems. During a single sequential scan, Diva inserts every $T$T-th key into the trie and builds each Infix Store in order. Because infixes are encountered in increasing order, occupieds bits are set and remainders are appended to runs sequentially. When a new quotient appears or an Infix Store fills, the corresponding runend bit is set. This makes construction efficient and friendly to hardware prefetching.

The trie implementation is also important to query performance. Diva needs a cache-aware structure supporting predecessor and successor searches. A traditional binary trie can cause many cache misses, so the system can use a high fanout Wormhole-style trie. This structure groups samples into balanced trees and indexes group boundaries with a trie, reducing predecessor and successor search cost to $O(\log_2 L)$O(log2​L) cache misses, where $L$L is the average key length.

For dynamic datasets, Diva extends the static design with insertion, deletion, and resizing support. Infix Stores overprovision slots to absorb new insertions. Their runs are evenly spaced using a linear mapping based on quotient order, and insertions or deletions can shift runs left or right in a manner similar to Robin Hood hashing. Overflow or underflow triggers resizing and remapping.

New keys also update the distribution model. With probability $\frac{1}{T}$T1​, an inserted key becomes a new trie sample; with probability $1 - \frac{1}{T}$1−T1​, its infix is inserted into the current Infix Store. When a new sample is inserted, the corresponding Infix Store is split into two stores, one containing smaller keys and one containing larger keys. When a sample is deleted, neighboring stores can be merged. Because new samples can bring predecessor and successor keys closer together, older infixes may become shorter and carry less resolution. Diva handles variable-length infix information by encoding shorter infixes with unary padding and optionally widening slots over time to maintain a stable false positive rate. During queries, missing bits from shorter infixes are treated as wildcard bits.

Experiment

The evaluation covers theoretical false positive guarantees, static and dynamic range-filter benchmarks on integer and variable-length key datasets, and an integration with a B-tree key-value store. These experiments validate that Diva maintains low false positive rates across short and long range queries while remaining query-fast and memory-controlled, unlike baselines whose accuracy or latency degrades as query length, dataset size, or workload skew increases. Dynamic tests further show that Diva supports efficient insertions and deletions, respects its memory budget better than competing expandable filters, and accelerates end-to-end empty range queries in WiredTiger.

The provided context defines core symbols for range filtering and introduces Diva as a range filter that uses sampled keys in a trie and Infix Stores to represent key ranges. It supports low false positive rate, arbitrary query sizes, variable length keys, dynamic updates, deletes, resizability, and strong query and construction performance. Diva maintains an accurate distribution model through trie samples, giving lower false positive rates than Memento filter and better update behavior than SNARF. Diva provides the fastest deletions among tested filters by limiting shifting and rewriting through Infix Store splitting. In integrated key value workloads, Diva greatly improves end to end empty range query latency and also outperforms Memento filter by supporting variable length queries.

The comparison shows that existing range filters support only parts of the desired capabilities, while Diva is presented as the first filter combining variable-length queries, variable-length keys, and dynamic updates. Experimental context also describes Diva as maintaining low false positive rates across query lengths and expansions while using its memory budget more consistently than compared dynamic filters. When integrated into a storage engine, Diva provides much faster empty range query processing than baselines and filters with weaker query flexibility. Diva uniquely combines support for variable-length queries, variable-length keys, and dynamic operation. Diva avoids the memory expansion waste seen in a compared dynamic filter during insertions. Diva delivers faster deletions and stronger end-to-end empty range query performance than compared dynamic filters.

The compared range filters show different tradeoffs among construction time, memory use, update cost, and query cost. Filters that support robust range filtering over longer queries generally require more memory, while some designs depend on hash count, key length, false positive target, or distribution modeling. Diva is presented as using low cost bulk construction with sequential memory access and favorable operation costs for empty and non empty range queries. Diva benefits from sequential bulk construction and minimal hashing, giving it a strong construction time advantage over the compared designs. Range query costs vary across filters, with some depending mainly on key length and others on false positive target or hash count. Update support is limited to a subset of filters, and update speed can degrade when distribution models or data structures grow with dataset size.

Diva derives each key's infix by removing common prefix bits, bits redundant with a sample's predecessor and successor, and the suffix. The examples show that this leaves only differentiating bits, producing compact identifiers for range filtering. The accompanying results describe Diva as accurate, memory bounded, fast for updates, and better than Memento filter on long range queries. Diva compactly encodes keys by dropping shared, redundant, and suffix bits. Diva respects memory budgets while beating SNARF on updates and Memento filter on long queries.

The experiments evaluate Diva against existing range filters and storage engine baselines across supported capabilities, construction cost, memory usage, query cost, and update performance. The results validate that Diva uniquely supports variable-length keys, variable-length queries, and dynamic updates while maintaining low false positives and consistent memory utilization. Qualitative findings also show that Diva achieves strong construction time, faster deletions and updates than selected baselines, and lower empty range query latency in end-to-end workloads.