Source-linked AI summary
A Model for Learned Bloom Filters, and Optimizing by Sandwiching
Michael Mitzenmacher
TL;DR
Learned Bloom filters augment standard Bloom filters with machine-learned pre-filters, but require a formal account of their guarantees and query-dependent behavior. The paper supplies that model, derives optimization guidance including sandwiching, and extends the approach to learned Bloomier filters.
Problem
Prior work proposed learned Bloom filters without a suitable mathematical model for judging their performance and guarantees.
Method
The paper formally models learned Bloom filters, analyzes query-distribution-dependent false positives, optimizes them by sandwiching, and applies the framework to learned Bloomier filters.
Results
The analysis clarifies which guarantees learned Bloom filters provide, estimates when the learned function can improve performance, and shows how sandwiching can improve the structure.
Takeaways & Limitations
Learned Bloom filters may be effective for sets accurately predicted by small learned functions, but their implications should be considered before adoption.
Takeaways & Limitations
Their false-positive behavior depends on the query distribution, and changes between test and future-query distributions can limit the analysis’s guidance.
Abstract
from arXiv · showhide
Recent work has suggested enhancing Bloom filters by using a pre-filter, based on applying machine learning to determine a function that models the data set the Bloom filter is meant to represent. Here we model such learned Bloom filters,, with the following outcomes: (1) we clarify what guarantees can and cannot be associated with such a structure; (2) we show how to estimate what size the learning function must obtain in order to obtain improved performance; (3) we provide a simple method, sandwiching, for optimizing learned Bloom filters; and (4) we propose a design and analysis approach for a learned Bloomier filter, based on our modeling approach.
1 Introduction
The paper develops a formal model for learned Bloom filters, addressing missing performance guarantees and introducing optimization and related-structure extensions.
- 1 Introduction: The paper formalizes learned Bloom filters because prior work did not provide a suitable mathematical model for evaluating them.
- 1 Introduction: Learned Bloom filters use a learned pre-filter and a smaller backup Bloom filter to represent a set while preventing false negatives.The learned function estimates membership and the backup filter checks keys the function would otherwise reject.
- 1 Introduction: The model clarifies their guarantees, estimates the required learned-function size, provides optimization methods, and extends to related structures.
- 1 Introduction: The analysis shows that sandwiching—with Bloom filters before and after the learned function—can improve the structure’s performance.The paper explains this improvement mathematically and intuitively.
- 1 Introduction: The paper emphasizes foundational analysis to clarify both the potential and pitfalls of machine-learning components in data structures.
2 Review: Bloom Filters
Standard Bloom filters provide compact set representations with no false negatives and concentrated false-positive behavior under their hashing assumptions, but have practical and adversarial limitations.
- 2 Review: Bloom Filters: A Bloom filter represents a set with an m-bit array and k hash functions, returning possible membership without false negatives.Queries are answered by checking whether all corresponding hashed bits are set.
- 2 Review: Bloom Filters: The false-positive probability is governed by the fraction of bits set and is tightly concentrated around its expectation in the typical parameter regime.
- 2 Review: Bloom Filters: For a priori query sets independent of the hash functions, the observed false-positive rate is similarly concentrated near the theoretical probability.
- 2 Review: Bloom Filters: The term false positive rate can mean different things in Bloom-filter and learning-theory contexts, so its interpretation requires care.
- 2 Review: Bloom Filters: Fully random hashing is an idealization that appears reasonable in many practical cases, while adversarial access can expose false positives.
- 2 Review: Bloom Filters: Standard Bloom filters support insertions easily but do not naturally support deletions, motivating alternatives such as cuckoo filters.
3 Learned Bloom Filters
Learned Bloom filters combine a learned classifier with a backup filter, but their false-positive behavior depends on the query distribution and can change when workloads shift.
- 3.1 Definition of the Data Structure: A learned Bloom filter thresholds a neural network’s membership estimate and uses a backup Bloom filter for keys below the threshold.This backup prevents false negatives caused by the learned model.
- 3.1 Definition of the Data Structure: Its performance improves only when representing the learned function and backup filter requires less space than a standard Bloom filter at the same false-positive rate.
- 3.2 Defining the False Positive Probability: The false-positive rate is not query-independent: queries concentrated where the learned function exceeds the threshold can produce substantially more false positives.The paper’s range example contrasts concentrated queries with uniformly random queries.
- 3.2 Defining the False Positive Probability: A learned Bloom filter’s false-positive rate is defined with respect to a query distribution and includes the backup filter’s false-positive behavior.
- 3.2 Defining the False Positive Probability: Under matching test and future-query distributions, empirical false-positive rates can predict future behavior using concentration bounds.If the distributions differ, the paper states that the resulting theorem offers limited guidance.
- 3.3 Additional Learned Bloom Filter Benefits and Limitations: Insertions can be handled by adding keys to the backup filter, but deletions are not natural and may turn deleted keys into false positives.
- 3.3 Additional Learned Bloom Filter Benefits and Limitations: Substantial data changes or excessive false positives may require relearning, which requires access to the original set and additional negative examples.
4 Size of the Learned Function
The paper models how large the learned function must be for a learned Bloom filter to outperform a standard Bloom filter, using oracle error rates and a space-based false-positive model. The analysis yields practical estimates, including a worked case where a 3-bit-per-item learned function reduces false positives by over 10% at no extra space.
- Model assumptions: The model treats the learned function as an oracle with false-positive probability Fp on non-keys and false-negative fraction Fn among keys.In practice, Fp depends on the query stream and may be measured empirically; different oracle choices can be evaluated separately.
- Model assumptions: The backup filter stores only mFn keys, so its budget of bm bits corresponds to b/Fn bits per stored key.The model assumes a Bloom filter using j bits per stored key has false-positive rate α^j.
- False-positive model: The learned Bloom filter has false-positive rate Fp + (1 − Fp)α^b/Fn, combining errors from the learned function and backup Bloom filter.A non-key either triggers a false positive in f or, otherwise, in the backup filter.
- Comparison with standard Bloom filters: Using the same total space bm + ζ bits, a standard Bloom filter has false-positive probability α^b+ζ/m; improvement therefore depends on the learned function's bits-per-key bound.The paper expresses the improvement condition as a bound on ζ/m.
- Worked example: With Fp = 0.01, Fn = 0.5, and a one-byte-per-item target, using at most 3 bits per item for f lowers false positives from approximately 0.0214 to 0.0181.The backup filter uses 5m bits, producing over a 10% reduction in false positives with the same or less space.
- Practical use: The analysis is useful for testing candidate thresholds and learned-function sizes before conducting extensive experiments.Practitioners can estimate Fp and Fn for alternatives and apply the equations to assess expected performance.
- Scaling question: Effectiveness on growing data sets depends on whether the information needed by f grows sublinearly with |K|.For a set of consecutive integers, the key set can be represented by two integers independent of |K|.
5 Sandwiched Learned Bloom Filters
The sandwiched learned Bloom filter places Bloom filters before and after the learned function, improving false-positive performance under the paper’s model. Its optimal backup filter has a fixed size, while additional budget is assigned to the initial filter.
- 5.1 The Sandwich Structure: The sandwiched design uses an initial Bloom filter to reject many nonmembers, a learned function to remove false positives, and a backup filter to restore learned-function false negatives.The initial filter passes all matching keys to the learned function rather than declaring membership; the backup filter admits keys in K rejected by f.
- 5.2 Analyzing Sandwiched Learned Bloom Filters: The modeled false-positive rate is α^b1(Fp + (1 − Fp)α^(b2/Fn)), combining the initial-filter pass probability with false positives from f and the backup filter.The analysis assumes a total budget of bm bits divided into b1m and b2m bits, with the backup filter storing mFn keys.
- 5.2 Analyzing Sandwiched Learned Bloom Filters: The optimal backup-filter allocation b2 = b*2 is a constant independent of the total budget b, so extra budget should increase the initial filter once the backup is appropriately sized.This allocation follows from minimizing the modeled false-positive expression; the initial filter is unnecessary only when the best backup allocation already uses the full budget.
- 5.2 Analyzing Sandwiched Learned Bloom Filters: At b = 8 bits per key, the false positive rate drops from approximately 0.010045 to 0.005012, over a factor of 2, when using the initial Bloom filter.At b = 10 bits per key, it drops from approximately 0.010066 to 0.001917, almost an order of magnitude.
- 5.2 Analyzing Sandwiched Learned Bloom Filters: For Fp = 0.01, Fn = 0.5, and α = 0.6185, sandwiching yields a gain whenever the oracle size ratio ζ/m is below approximately 3.36.For sufficiently large b and optimal b2, the improvement does not depend on the exact total budget b.
- 5.2 Analyzing Sandwiched Learned Bloom Filters: The initial Bloom filter can mitigate distribution shift in learned-function queries, but sandwiching may require more hashing and memory accesses, making overall efficiency implementation dependent.The distribution-shift issue then affects only the smaller number of keys passing the initial filter.
6 Learned Bloomier Filters
The paper extends learned Bloom-filter analysis to learned Bloomier filters, which return values for set keys and may produce non-null false positives outside the set.
- Learned Bloomier filters associate each key in K with a value and aim to return null for keys outside K.
- The paper derives performance formulae for learned Bloomier filters using its learned Bloom-filter modeling approach.
7 Conclusion
The conclusion emphasizes formal analysis, query-set-dependent false-positive behavior, sandwiching optimization, and generalization to Bloomier filters. It cautions that learned Bloom filters require careful consideration, while small accurately predictable sets may achieve significant improvements.
- The analysis examines how the query set affects the reported false-positive rate and which applications learned Bloom filters suit.
- The modeling yields a natural sandwiching optimization and generalizes to related structures such as Bloomier filters.
- Learned Bloom filters may significantly outperform standard variants when small learned functions accurately predict the represented sets.
8 Supplemental: Learned Bloomier Filters Derivation
The learned Bloomier construction combines a learned oracle with a Bloom filter for oracle errors and a backup Bloomier filter for recovery. Its model accounts for oracle and backup false positives and motivates the space trade-off when false negatives are sufficiently low.
- A learned Bloomier filter maps each key to a value, while treating an incorrect non-null value for a key in K as a false negative.
- The learned oracle is followed by a Bloom filter storing oracle false negatives, with a backup Bloomier filter recovering their correct values.
- The model represents mFn oracle false negatives using b mFn Bloom-filter bits and assigns the oracle a false-positive probability Fp.
- A Bloomier filter for z keys uses c z(u + r) space and has false-positive probability 2^-r under the stated construction.
- The learned construction can incur false positives from both the oracle and backup Bloomier filter after Bloom-filter hits.
- Because Bloomier filters store values, sufficiently low false negatives may leave space for the learned function and an additional Bloom filter.