3 Approximate Membership: Bloom filter and Quotient filter

This chapter introduces approximate membership data structures for massive data processing, centering on Bloom filters and quotient filters. It explains why these compact structures are so widely used in networks, storage systems, and streaming pipelines: they provide fast insert and lookup with small memory footprints at the cost of controlled, one-sided errors. The text balances practice and theory—showing how to implement and tune parameters, deriving key formulas and lower bounds, and surveying real deployments—before contrasting Bloom and quotient filters to clarify when each is a better fit.

The Bloom filter portion covers mechanics (a bit array plus k hash functions), operations (O(k) insert/lookup), and error behavior (false positives but no false negatives), highlighting scenarios where most queries are absences. It illustrates production use in systems such as SST-based stores, web proxies, and light cryptocurrency clients, and provides a simple Python implementation. A configurable framework relates space, dataset size, number of hashes, and false-positive rate, with practical guidance like choosing k ≈ (m/n)·ln 2 and noting that unsuccessful lookups typically terminate after one or two probes. The chapter derives the standard error formula, argues via concentration bounds that it is tight in practice, and compares Bloom filters to theoretical lower bounds, showing they are close to optimal. It also surveys adaptations (e.g., counting, weighted, and adaptive variants) and candidly discusses limitations such as deletions and resizing.

The quotient filter section presents a compact, linear-probing hash-table design that stores fingerprints via quotienting (splitting into bucket index and remainder) and uses three metadata bits to maintain runs and clusters. This enables efficient deletion, resizing, and fast linear-time merging—capabilities that make quotient filters attractive in dynamic, distributed settings—at the expense of extra CPU work for decoding and tighter sensitivity to load factor. The chapter analyzes space/error trade-offs (fingerprint length versus false positives), notes that quotient filters are usually slightly larger than Bloom filters at common error targets but can be better at extremely low rates, and summarizes empirical comparisons: quotient filters tend to have faster inserts and successful lookups until high occupancy, while Bloom filters excel at uniform negative lookups and show steadier performance. The guidance closes with workload-driven recommendations based on throughput, CPU locality, deletion and resizing needs, and storage medium characteristics.

: Bloom filters in distributed storage systems. In this example, we have 50 Sorted String Tables (SSTs) on disk, and each table has a dedicated Bloom filter that can fit into RAM due to its much smaller size. When a user does a lookup, the lookup first checks the Bloom filters, thus avoiding expensive disk seeks.

: Example of insert into Bloom filter. In this example, an initially empty Bloom filter has m=8, and k=2 (two hash functions). To insert an element x, we first compute the two hashes on x, the first one of which generates 1 and the second one generates 5. We proceed to set A[1] and A[5] to 1. To insert y, we also compute the hashes and similarly, set positions A[4] and A[6] to 1.

: Example of a lookup on a Bloom filter. To do a lookup on x, we compute the hashes (which are the same as in the case of an insert), and we return Found/Present, as both bits in corresponding locations equal 1. Then we do a lookup of an element z, which we never inserted, and its hashes are respectively 4 and 5, and bits at locations A[4] and A[5] equal 1, thus we again return Found/Present.

: Usage of Bloom filter in Squid web proxy. A user requests a web page x, and a web proxy A can not find it in its own cache, so it locally queries the Bloom filters of B, C and D. The Bloom filter for D reports Present, so the request is forwarded to D. The resource is found at D and returned to the user.

: In Bitcoin, light clients can broadcast what transactions they are interested in, and thereby block the deluge of updates from the network.

: The plot relating the number of hash functions (k) and the false positive rate (f) in a Bloom filter. The graph shows the false positive rate for a fixed bits-per-element ratio (m/n), different curves corresponding to different ratios.

: The inequality describing the space-error lower bound.

: Quotienting in a hash table. The item y has the hash 10100 101101, therefore the remainder 101101 (35) will be stored in the slot determined by quotient, at bucket 10100 (20).

: Insertion into quotient filter and metadata bits.

: Insertion of y and z into the quotient filter.

:11: The memory layout of quotient filter slots.

: Resizing a quotient filter of size 4 that contains 3 elements. For the sake of simplicity, we assume that no collisions occurred between those 3 elements and ever remainder is stored in its original bucket. A fingerprint 110010 that hashed to bucket 11 (with remainder 0010) in the original quotient filter gets stored at 110 bucket of the second quotient filter (with remainder 0010), and in a 1100 bucket of the final quotient filter (with remainder 010.)

: Performance comparison of Bloom filters and quotient filters on inserts, uniform random lookups, and successful lookups, respectively.

• Bloom filters have been widely applied in the context of distributed databases, networks, bioinformatics, and other domains where regular hash tables are too space-consuming.
• Bloom filters trade accuracy for the savings in space, and there is a relationship between the space, false positive rate, the number of elements and the number of hash functions in the Bloom filter.
• Bloom filters do not meet the space vs. accuracy lower bound, but they are simpler to implement than more space-efficient alternatives, and have been adapted over time to deal with deletes, different query distributions, etc.
• Quotient filters are based on compact hash tables with linear probing and are functionally equivalent to Bloom filters, with the benefit of spatial locality, ability to delete, merge and resize efficiently.
• Quotient filters are based upon the space-saving method of quotienting and extra metadata bits that allow the full fingerprint reconstruction.
• Quotient filters offer better performance than Bloom filters on uniform random inserts and successful lookups, while Bloom filters win over on uniform random (unsuccessful) lookups. The performance of quotient filters is dependent on a load factor (lower load factor is better), and the performance of Bloom filters is dependent on the number of hash functions (fewer hash functions is better).

FAQ