PaperlayerView exact revision on arXiv

Source-linked AI summary

Diva++: Dynamic Range Filtering over Hard Workloads

Navid Eslami, Ioana O. Bercea, Niv Dayan

arXiv:2608.27616v1cs.DS

TL;DR

Existing range filters lack a simultaneous solution for strong FPR and performance guarantees, variable-length keys and ranges, and dynamic updates. Diva combines distribution-aware sampling with compressed infixes and dynamic stores, while Diva++ removes redundancy for jagged workloads. The designs are theoretically analyzed and empirically shown to support these capabilities with competitive FPR on real-world datasets.

  • Problem

    Existing range filters do not simultaneously provide FPR or performance guarantees, variable-length keys and queries, and dynamic updates.

  • Method

    Diva samples keys into a trie, compresses intervening keys into fixed-length infixes, and stores them in dynamically splittable blocks; Diva++ adds entropy encoding and binary tries for jagged distributions.

  • Results

    Diva and Diva++ provide variable-length query and key support, dynamicity, and high performance, with excellent or state-of-the-art FPR on real-world datasets.

  • Takeaways & Limitations

    Diva and Diva++ jointly address the six stated range-filtering goals across common and jagged real-world data distributions.

  • Takeaways & Limitations

    Diva's FPR guarantee is data-oblivious and applies to well-behaved smooth distributions, while the adopted notion is weaker than data-aware FPR.

Abstract

from arXiv · show

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 searching for them in storage. However, all existing range filters exhibit at least one of three shortcomings: (1) they do not provide any false positive rate or performance guarantees, (2) they do not support variable-length keys and query ranges, and (3) they do not allow dynamic updates. 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 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 differentiate the keys in 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 mathematically prove that Diva provides the best possible trade-off between memory and false positive rate on many common real-world data distributions. We extend these benefits to a wider range of real-world workloads by introducing Diva++, an enhanced Diva variant. Diva++ saves memory by removing redundancies among infixes using order-preserving entropy encoding. It then removes any remaining identical infixes and uses the freed space to store more bits of the original keys within compact binary tries. We compare Diva and Diva++ to all prior range filters, and show that they achieve 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.

1 INTRODUCTION

Range filters compactly test whether a key range is empty, but prior designs miss combinations of low FPR, broad query and key support, dynamicity, and speed. Diva addresses these goals through sampled tries and compressed infixes, while Diva++ reduces infix redundancy for jagged distributions.

  • Range Filters and Applications: Range filters answer approximate range-emptiness queries without false negatives, helping avoid redundant disk reads and network hops.They may return false positives, with the false positive rate depending on memory footprint.
  • Design Contentions: Existing range filters do not simultaneously achieve low FPR, arbitrary query lengths, variable-length keys, dynamic updates, and high operation performance.An information-theoretic lower bound also rules out achieving the lowest FPR and arbitrary query lengths together for worst-case workloads.
  • Core Contribution: Diva: Diva samples ordered keys into an S-Trie, removes common prefixes and suffixes, and retains fixed-length infixes that usually differentiate keys between samples.The S-Trie separates dense and sparse regions, while infix stores support efficient sequential processing and dynamic splitting.
  • Diva++: Diva++ targets jagged string distributions by entropy-encoding keys, eliminating repeated infixes, and storing additional differentiating bits in a binary data trie.These techniques reduce redundancy and increase the likelihood that infixes distinguish keys from range-query endpoints.
  • Additional Contributions: The authors quantify distribution conditions for low FPR and memory use, prove filter properties and lower bounds, and evaluate Diva and Diva++ in static, dynamic, and end-to-end settings.The evaluation includes WiredTiger, a B-Tree-based key-value store.

2 PROBLEM ANALYSIS

Range-filter designs face trade-offs among false-positive rate, memory, query flexibility, dynamicity, and speed. Existing approaches leave important goals unmet, while lower bounds show that robust support for long or variable-length ranges requires substantial memory.

  • Memory lower bounds: Robust range filters supporting queries up to length R require at least log2 R ε−O(1) bits per key.The bound implies that answering longer ranges requires more memory because the filter must represent more empty regions of the key space.
  • Memory lower bounds: With a 16 BPK budget and target FPR ε=0.01, a robust range filter can answer ranges of length at most 512.The passage notes that such short query lengths limit applicability.
  • Memory lower bounds: Robust support for variable-length keys would require infinite memory because infinitely many keys can occur within a range.Thus robustly attaining low FPR, arbitrary range lengths, and variable-length keys simultaneously is impossible.
  • Prior approaches: SNARF and Oasis+ assume fixed-length keys or have slow or disallowed dynamic operations, and both use binary search for queries.SNARF rewrites entire blocks for updates, while Oasis+ prunes empty regions and disallows dynamic operations.
  • Prior approaches: Bloom-filter-based range filters cannot generally support deletes or expansions without introducing additional mechanisms.Their bitmaps are optimized for memory but cannot reset or remap set bits directly.
  • Unmet goals: No existing range filter achieves all four goals: low FPR and memory use, variable-length queries, variable-length keys, and dynamic updates.The comparison also examines query and construction performance as separate goals.

3 DIVA

Diva is a range filter designed to support low false positive rates, variable-length keys and queries, dynamic operations, and high query and construction performance. It learns the dataset distribution with sampled keys, compresses intervening keys into infixes, and stores them in dynamic Infix Stores for range processing.

  • Sampling Keys and Deriving Infixes: For keys between adjacent samples, Diva removes the longest common prefix and truncates suffixes while retaining a fixed-length infix that differentiates keys and controls the FPR.The infix length is denoted m_infix, and the removed prefix can be inferred from the S-Trie.
  • Sampling Keys and Deriving Infixes: Diva samples every T-th ordered key into an S-Trie that approximates the dataset distribution and separates dense from sparse regions.Smaller T improves approximation accuracy but increases the S-Trie’s memory footprint.
  • Sampling Keys and Deriving Infixes: Diva allocates more effective resolution to dense key-space regions because longer shared prefixes free memory for retaining lower-order bits.This supports fine-grained queries in dense regions and coarse-grained queries in sparse regions.
  • False Positive Rate: 1 byte per infix yields an FPR of ≈3%, while the formal FPR guarantee is semi-robust and assumes a well-behaved dataset distribution.Diva’s infix encoding is described as providing a similar FPR-versus-memory trade-off to Bloom and Cuckoo filters.
  • Querying and Performance: Diva’s false positives arise from query-key infix collisions, while sequential memory accesses and minimal hashing overhead support fast construction.The S-Trie learns the data distribution, making low FPR most likely when queries follow that distribution.
  • Dynamicity: Diva stores infixes in dynamic Infix Stores and supports updates with approximately 1 BPK more memory than the static variant.Dynamic stores stretch to absorb insertions and split when a new sample divides an existing store; these splits increase FPR logarithmically.

4 DIVA++

Diva++ extends Diva to jagged data distributions by removing redundancies among infixes, improving distinguishability without added memory overhead. It combines order-preserving entropy encoding with bit-level full key differentiation and supports dynamic operation adaptations.

  • Motivation: Jagged key distributions create redundant, indistinguishable infixes that can increase the false positive rate.This is especially problematic when query endpoints follow a distribution similar to the dataset.
  • Overview: Diva++ extends Diva’s FPR guarantees to a broader class of jagged data distributions without the memory overhead of storing more samples or longer infixes.The extension uses two complementary techniques to distinguish adjacent infixes.
  • Order-Preserving Entropy Encoding: Order-preserving entropy encoding removes common bits among adjacent keys, flattening distributions and allowing more distinguishing information in each infix.Mehlhorn’s bisection preserves lexicographic order while producing near-optimal prefix codes; encoded representations can be used directly during queries.
  • Order-Preserving Entropy Encoding: Second-order entropy encoding extends Diva’s FPR bounds to distributions without third- or higher-order patterns by making encoded infixes more uniformly distributed.Uniformly distributed infixes make negative query endpoints less likely to match an infix.
  • Bit-Level Full Key Differentiation: When entropy encoding leaves identical infixes, Diva++ stores one representative and uses the freed space to differentiate keys in compact D-Tries.BITR encodes each D-Trie’s topology and edge labels in at most two bits per node.
  • Bit-Level Full Key Differentiation: Elias-Gamma coding avoids wasting space on long D-Trie paths caused by higher-order bit patterns.In the URLs dataset, approximately 14% of D-Tries have paths longer than 50 edges.
  • Bit-Level Full Key Differentiation: Diva++ uses binary tries at bit granularity to avoid duplicate edge-label bits and improve space efficiency at the same FPR level.The reported memory improvement is 9× relative to the original Diva design.
  • Dynamic Extension: Diva++ trades additional D-Trie parsing and searching cost for better key differentiation and significantly lower FPR.The dynamic design also handles cases where truncated existing keys lack bits needed to distinguish later insertions, supporting insertions and deletions.

5 THEORETICAL ANALYSIS AND RESULTS

Diva’s theoretical guarantees depend on well-behaved distributions and data-oblivious queries, while Diva++ broadens the supported distributions through entropy encoding and duplicate elimination. The analysis establishes FPR bounds, memory costs, cache efficiency, and lower bounds limiting stronger guarantees.

  • FPR Analysis: Diva bounds the probability that a particular infix exists by analyzing the data distribution’s probability mass within its corresponding sub-range.The analysis denotes this probability P_k,n and uses it to derive false-positive guarantees.
  • FPR Analysis: Uniform, normal, and power law distributions satisfy the paper’s well-behavedness conditions under the stated parameter requirements.Uniform distributions are trivially well-behaved; normal and power law examples satisfy corresponding scale conditions.
  • FPR Guarantees: At most ϵ is the static point-query FPR for Diva, while the static range-query FPR is at most 2ϵ on well-behaved distributions.These are the guarantees stated in Theorem 5.3.
  • FPR Guarantees: The dynamic variant’s expected FPR is at most ϵ/2 · (log2 N + 2) for point queries and ϵ · (log2 N + 2) for range queries.Theorem 5.4 gives these bounds for dynamic operations.
  • Diva++ Guarantees: Diva++ extends Diva’s semi-robust guarantees to jagged distributions through k-th order entropy encoding and can become robust with infinite-order encoding.The encoding makes resulting infixes uniformly distributed for datasets without higher-order patterns than k.
  • Memory and Performance: Diva++ preserves Diva’s memory footprint on well-behaved data, while D-Trie encoding consumes at most 2 bits per node.Experiments found D-Tries’ reclaimed duplicate-infix space offset their memory use.
  • Memory and Performance: Diva and Diva++ require an expected O(log2 L) cache misses, becoming constant for fixed-length keys.The bound follows from trie operations and expected single-cache-miss Infix Store access.
  • Memory Lower Bounds: Data-aware FPR guarantees require substantially more memory: with variable-length keys or ranges, the lower bound implies storing the full dataset.The paper states this follows because R = ∞ in those cases.

6 EVALUATION

Evaluation shows that Diva and Diva++ balance false-positive rate, query speed, construction time, and dynamicity across smooth, jagged, and expanding workloads. Diva++ improves FPR on difficult distributions, while its D-Tries add query overhead.

  • Static Evaluation: Robust range filters’ FPR approaches one as query length increases, while their longer queries also incur substantially more cache misses.The paper attributes this deterioration to extra internal probes.
  • Static Evaluation: Diva stores more key information at the same memory footprint than SuRF, yielding at least an order-of-magnitude lower FPR across experiments.SuRF explicitly stores sufficiently long prefixes, whereas Diva exploits learned local distribution uniformity.
  • Static Evaluation: Diva++ matches Diva on Uniform and Normal datasets but achieves a 2× lower FPR across all range-query lengths on Books and OSM.Duplicate infixes from skewed distributions motivate Diva++’s D-Trie differentiation.
  • Static Evaluation: Diva and Diva++ provide the best balance between FPR and query speed for variable-length range queries.Figure 12 reports that filters beating them on FPR have significantly slower queries, and vice versa.
  • Static Evaluation: Diva++ improves Diva’s FPR by as much as 3× on the Normal dataset, in exchange for 2× slower queries.The slowdown comes from parsing more complex D-Tries.
  • Static Evaluation: On EnWiki, Emails, and URLs, the original Diva and SuRF versions have FPRs of 40% or higher because of jagged key distributions.Entropy encoding alone improves both filters by as much as 4×, while combining it with full-key differentiation gives Diva++ the lowest FPRs.
  • Construction Times: Diva and Diva++ construct significantly faster than other range filters, with the closest competitor taking 2.7× longer.Their advantage is attributed to sequential memory access.
  • Dynamic Evaluation: During expansions, Diva and Diva++ maintain the lowest FPR for range queries of any length, support fast insertions, and respect the memory budget.Other filters either are not expandable or experience FPR and memory degradation after insertions.

7 FUTURE DIRECTIONS

The authors identify integration into OrcaDB and broader storage-engine research as future directions for Diva and Diva++.

  • Future Directions: The authors are integrating Diva into OrcaDB, their fork of RocksDB, to address slow range queries in LSM-trees.They also identify adaptivity and related storage-engine directions for future research.

8 CONCLUSION

The paper presents Diva as a range filter that simultaneously supports low FPR and memory use, flexible queries and keys, dynamicity, and high performance. Its theoretical and empirical results support this combination.

  • Conclusion: Diva simultaneously attains the six range-filtering goals, including low FPR, arbitrary range lengths, variable-length keys, dynamicity, and high query and construction performance.The conclusion says these properties are supported theoretically and empirically.

A PROOF OF LEMMA 3.1

The proof bounds how many infix values can occur between predecessor and successor boundaries. Increasing the infix length exponentially expands this representable range, with a special-case increment when necessary.

  • The difference between predecessor and successor infix prefixes grows by at least a factor of two at each increment.The proof starts from an initial difference of at least three and derives a doubling lower bound at every iteration.
  • After k iterations, the number of potential infix values is at least 2^k + 2.
  • With m_infix − 2 = ⌈log2 ε⌉ − 2 steps, the number of potential values reaches at least the target bound.The supplied proof passage states this progression before completing the target expression.
  • Diva increments m_infix only for the affected Infix Store when the default length would represent too few values.This handles predecessor-successor configurations that fall below the lemma’s guaranteed capacity.

B PROOF OF THEOREM 5.2

The proof analyzes infix-generation probabilities within sampled-key intervals and bounds their deviations using density smoothness and sample-gap concentration. Under well-behaved distributions, the resulting error terms remain controlled, including in the dynamic case.

  • Each Infix Store partitions the interval between consecutive samples into Δ equal-width sub-ranges, each associated with a distinct infix.
  • The probability that a key generates a particular infix is expressed conditionally through the store probability δ_k and sub-range probability P_k,n.The sub-range is (s_n, s_n+1], and P_k,n is defined by its CDF mass.
  • Taylor approximation bounds P_k,n in terms of interval length l_k, while a second bound relates δ_k to the same interval length.
  • For well-behaved distributions, f(x_k) controls the dominant term, while E1 and E2 are low-order errors when density and derivative bounds hold.The conditions require f(x) to stay within specified bounds and f′(x) not to be too large.
  • 1/6 + 49/72 bounds the combined error terms by at most 1, establishing the main claim under the stated conditions.
  • With high probability, δ_k is bounded by δ for all k, while dynamically the expected probability of seeing a given infix is at most ε.The static proof uses a union bound over T keys; the dynamic case relies on an expected store size of T.

C PROOF OF THEOREM 5.6

The proof establishes a memory lower bound for data-oblivious range filters through an encoding argument. If a filter used substantially less than the bound, it would encode uniformly random key sets beyond their entropy.

  • The encoding argument applies to range filters with data-oblivious false positive rate ε, including both semi-robust and robust filters.
  • Using less than log2(1/ε) bits per key would encode random key sets beyond the entropy limit, which is impossible.
  • The proof considers N-key sets sampled uniformly from a universe of size u much larger than N.
  • The filter’s expected number of positive responses over universe keys is bounded by the false positives ε·u plus the N true positives.
  • The filter representation together with the identities of returned true positives encodes the exact key set.

D PROOF OF THEOREM 5.7

The proof extends a range-filter lower bound from well-separated key sets to uniformly random datasets. Uniform random sets are well-separated with overwhelming probability when the universe is sufficiently larger than the dataset and separation scale.

  • The proof uses R-well-separated sets whose distinct keys differ by at least 2R and remain away from both universe boundaries.
  • Goswami et al.’s encoding argument shows that excessive accuracy or space efficiency would violate the entropy limit for this family.
  • Uniformly random key sets are used to generalize the lower bound to semi-robust filters because the uniform distribution is well-behaved.
  • When u is much larger than N and R, uniformly distributed datasets are R-well-separated with overwhelming probability.
  • For uniformly distributed data, the filter must use at least (1 − ...) log2(1/ε) − O(1) bits per key on average.

E PROOF OF THEOREM 5.8

The proof encodes uniformly random key sets using a range filter’s representation and queried interval outcomes, then compares the encoding length with the set’s entropy. This shows that a filter cannot simultaneously be too accurate and too space-efficient.

  • The proof uses an encoding argument: an overly accurate or space-efficient filter would encode random key sets below their theoretical entropy.The filter representation and query outcomes are supplemented with information that lets decoding recover the sampled key set.
  • The encoding queries three interval classes and records positives returned by the filter for each class.Class (A) uses regularly spaced ranges, class (B) uses larger ranges overlapping class-(A) non-empty ranges, and class (C) uses covering intervals around each key.
  • The filter’s guarantees bound expected positives for the three classes, with data-oblivious and data-aware expectations taken over different sources of randomness.The first inequality averages over random datasets, while the other inequalities average over the filter’s internal randomness.
  • The recursive final encoding step uses positive responses on covering intervals to determine which subinterval contains keys.For each non-empty interval, the procedure checks pairs of level-i covering intervals from larger to smaller scales.
  • The decoder reverses the encoding to recover the key set, so the average encoding size must be at least the entropy of a uniformly random set.The proof then analyzes the encoding size, applies Jensen’s inequality, and ignores an insignificant logarithmic term.
Loading 2608.27616v1…