Bloom filter

A Bloom filter is a compact, probabilistic representation of a set that supports insertion and membership queries^[1]. It is an array of $m$ bits, initially zero, and $k$ hash functions, each mapping an element to one of the $m$ positions. Adding an element sets the $k$ bits its hashes select. A query checks the same $k$ bits: if any is zero, the element was certainly never added; if all are one, it probably was, but the bits may have been set by other elements. A Bloom filter therefore has no false negatives and a tunable rate of false positives, and its size depends on the number of elements and the error rate, not on the size of the elements. Around 10 bits per element give a false-positive rate of 1%. The usual application is to avoid an expensive lookup, such as a disk read or a network request, for keys that are not there.

§ 01

Operation

An 18-bit filter with k = 3. Adding x and y sets six bits. The query for w finds its three bits set by x and y, a false positive; the query for z finds a zero bit and answers “no” without further work.

A filter cannot enumerate its elements or remove one: a set bit may be shared by several elements, and clearing it would create false negatives for the others. Two filters with the same size and hash functions can be combined: the bitwise OR of two filters is exactly the filter of the union of their sets, and the bitwise AND is a filter that contains the intersection, with a somewhat higher false-positive rate than a filter built from the intersection directly^[2].

A Bloom filter over strings, in a byte array.

(* A Bloom filter with m bits and k hash functions. The k positions are
   derived from two hashes by double hashing, g_i(x) = h1(x) + i h2(x). *)
type t = { bits : Bytes.t; m : int; k : int }
 
let create ~m ~k = { bits = Bytes.make ((m + 7) / 8) '\000'; m; k }
 
let positions f x =
  let h1 = Hashtbl.seeded_hash 17 x and h2 = Hashtbl.seeded_hash 91 x lor 1 in
  List.init f.k (fun i -> (h1 + i * h2) mod f.m)
 
let get f i = Char.code (Bytes.get f.bits (i / 8)) land (1 lsl (i mod 8)) <> 0
let set f i =
  Bytes.set f.bits (i / 8)
    (Char.chr (Char.code (Bytes.get f.bits (i / 8)) lor (1 lsl (i mod 8))))
 
let add f x = List.iter (set f) (positions f x)
let mem f x = List.for_all (get f) (positions f x)
 
(* Filters of the same size and hashes combine bitwise. *)
let union a b = { a with bits = Bytes.mapi (fun i ch ->
    Char.chr (Char.code ch lor Char.code (Bytes.get b.bits i))) a.bits }
 
let popcount f =
  let n = ref 0 in
  for i = 0 to f.m - 1 do if get f i then incr n done; !n

The $k$ hash functions need not be independent. Kirsch and Mitzenmacher showed that the positions $g_{i} (x) = h_{1} (x) + i h_{2} (x) mod m$ , computed from two hash values, give the same asymptotic false-positive rate as $k$ independent hashes^[3], which is what the code does.

§ 02

False-positive rate

Assume the hash functions choose positions independently and uniformly. After $n$ insertions, each of which sets $k$ bits, a given bit is still zero with probability

(1 - \frac{1}{m})^{k n} \approx e^{- k n / m}

A query for an element that was never added is a false positive if all $k$ of its bits are set. Treating the bits as independent gives the classical estimate

p \approx (1 - e^{- k n / m})^{k}

The bits are not quite independent, and Bose and co-authors showed that this formula slightly underestimates the true rate, although the difference vanishes as $m$ grows^[5]. For fixed $m$ and $n$ , the rate is minimized when

k = \frac{m}{n} ln 2, p = 2^{- k} \approx 0.618 5^{m / n}

at which point half the bits are set. Conversely, a target rate $p$ needs

\frac{m}{n} = \frac{lo g _{2} ( 1/ p )}{ln 2} \approx 1.44 lo g_{2} \frac{1}{p}

bits per element: 9.6 bits for 1%, 14.4 bits for 0.1%. Every factor of ten in the error rate costs 4.8 more bits per element. Carter and co-authors showed that any structure answering approximate membership queries with false-positive rate $p$ needs at least $lo g_{2} (1/ p)$ bits per element^[4], so a Bloom filter uses about 44% more space than the minimum.

Measuring the rate with 100,000 keys and a million queries for keys that were never added, at the best k for each size.

open Bloom
 
(* Insert n keys, then query a million keys that were never inserted. *)
let trial ~n ~bits_per_key =
  let m = n * bits_per_key in
  let k = max 1 (int_of_float (Float.round (float bits_per_key *. log 2.))) in
  let f = create ~m ~k in
  for i = 0 to n - 1 do add f (Printf.sprintf "user:%d" i) done;
  let q = 1_000_000 and fp = ref 0 in
  for i = 0 to q - 1 do if mem f (Printf.sprintf "guest:%d" i) then incr fp done;
  let predicted = (1. -. exp (-. float (k * n) /. float m)) ** float k in
  Printf.printf "%8d %3d %11.6f %11.6f\n" bits_per_key k
    (float !fp /. float q) predicted

Running it.

bits/key   k    measured   predicted
       4   3    0.146989    0.146892
       6   4    0.055956    0.056057
       8   6    0.021548    0.021577
      10   7    0.008372    0.008194
      12   8    0.003190    0.003142
      16  11    0.000463    0.000459
      20  14    0.000074    0.000067

§ 03

Counting elements

The number of set bits reveals roughly how many elements a filter holds. If $X$ of the $m$ bits are set, then inverting the expected fraction of zero bits gives the estimate^[11]

n \approx - \frac{m}{k} ln (1 - \frac{X}{m})

Applied to the union of two filters, it estimates the size of the union of the sets, and from that the size of their intersection.

Two overlapping sets of 12,000 keys, their union, and the estimates.

open Bloom
 
(* Estimate how many keys a filter holds from the number of set bits:
   after n insertions, about m (1 - e^(-kn/m)) bits are set. *)
let estimate f =
  let x = float (popcount f) and m = float f.m and k = float f.k in
  -. m /. k *. log (1. -. x /. m)

Running it.

estimated size of a:     11978 (true 12000)
estimated size of b:     11995 (true 12000)
estimated size of a + b: 19954 (true 20000)
u contains 3 and 19999:  true true

§ 04

Variants

Counting Bloom filters

Fan and co-authors replaced each bit with a small counter, typically four bits, so that deletion decrements the counters that insertion incremented^[6]. This costs four times the space, and deletion is only safe for elements known to be present: deleting an element that the filter merely reports as present decrements counters that belong to other elements, creating false negatives.

A counting filter, and the result of deleting a false positive.

(* A counting Bloom filter keeps a small counter per position instead of
   a bit, so an insertion can be undone. *)
type t = { c : int array; k : int }
let create ~m ~k = { c = Array.make m 0; k }
let positions f x =
  let m = Array.length f.c in
  let h1 = Hashtbl.seeded_hash 17 x and h2 = Hashtbl.seeded_hash 91 x lor 1 in
  List.init f.k (fun i -> (h1 + i * h2) mod m)
let add f x = List.iter (fun i -> f.c.(i) <- f.c.(i) + 1) (positions f x)
let remove f x = List.iter (fun i -> f.c.(i) <- f.c.(i) - 1) (positions f x)
let mem f x = List.for_all (fun i -> f.c.(i) > 0) (positions f x)

Running it.

after removing in7: mem in7 = false, mem in8 = true
false positive out13; removing it
keys now reported absent: in6, in86, in94

Blocked Bloom filters

A query for a present element reads $k$ random bits, which for a large filter means $k$ cache misses. A blocked Bloom filter first hashes the element to one cache line and then sets its $k$ bits within that line, which makes a query cost one cache miss at the price of a slightly higher false-positive rate^[9].

Cuckoo, quotient and xor filters

Filters that store short fingerprints of the elements in a hash table can come closer to the $lo g_{2} (1/ p)$ bound and can support deletion. Quotient filters store fingerprints in a compact linear-probing table^[13]. Cuckoo filters use cuckoo hashing with two candidate buckets per fingerprint; they support deletion and use less space than a Bloom filter for rates below about 3%^[7]. Xor filters, which are built once from a fixed set, use about $1.23 lo g_{2} (1/ p)$ bits per element and answer a query with three memory accesses^[8].

§ 05

Applications

Bloom's own example was hyphenation: of a dictionary of 500,000 words, most could be hyphenated by simple rules, and a filter held in memory identified the remaining words, whose hyphenation had to be read from disk, so that the disk was consulted for few words that did not need it^[1]. The same pattern recurs throughout systems. Bigtable keeps a Bloom filter for each of its on-disk tables so that a read for a row or column that is not there needs no disk access^[10], and log-structured storage engines such as LevelDB, RocksDB and Cassandra do the same. Web caches have exchanged Bloom filters that summarize their contents^[6], and routers and network monitors use them to track flows and packets^[2]. Bitcoin's lightweight clients once sent full nodes a Bloom filter of the addresses they cared about; Gervais and co-authors showed that such filters leak much of the information they were meant to hide^[12].

§ 06

History

Burton Howard Bloom described the method in 1970 as one of two hash-coding schemes that trade a small, controlled error rate for space^[1]. Carter, Floyd, Gill, Markowsky and Wegman established the lower bound on the space of approximate membership testers in 1978^[4]. The structure became widely used in networking in the late 1990s; Fan, Cao, Almeida and Broder introduced counting Bloom filters in their summary-cache protocol^[6], and Broder and Mitzenmacher's survey of 2004 collected its uses and gave it the “Bloom filter principle”: wherever a list or set is used and space is at a premium, consider a Bloom filter if the effect of false positives can be mitigated^[2]. The later fingerprint-based filters, cuckoo filters in 2014 and xor filters in 2020, improved on its space and speed^[7]^[8].