README.md
1# Boom Filters
2[![Build Status](https://travis-ci.org/tylertreat/BoomFilters.svg?branch=master)](https://travis-ci.org/tylertreat/BoomFilters) [![GoDoc](https://godoc.org/github.com/tylertreat/BoomFilters?status.png)](https://godoc.org/github.com/tylertreat/BoomFilters)
3
4**Boom Filters** are probabilistic data structures for [processing continuous, unbounded streams](http://www.bravenewgeek.com/stream-processing-and-probabilistic-methods/). This includes **Stable Bloom Filters**, **Scalable Bloom Filters**, **Counting Bloom Filters**, **Inverse Bloom Filters**, **Cuckoo Filters**, several variants of **traditional Bloom filters**, **HyperLogLog**, **Count-Min Sketch**, and **MinHash**.
5
6Classic Bloom filters generally require a priori knowledge of the data set in order to allocate an appropriately sized bit array. This works well for offline processing, but online processing typically involves unbounded data streams. With enough data, a traditional Bloom filter "fills up", after which it has a false-positive probability of 1.
7
8Boom Filters are useful for situations where the size of the data set isn't known ahead of time. For example, a Stable Bloom Filter can be used to deduplicate events from an unbounded event stream with a specified upper bound on false positives and minimal false negatives. Alternatively, an Inverse Bloom Filter is ideal for deduplicating a stream where duplicate events are relatively close together. This results in no false positives and, depending on how close together duplicates are, a small probability of false negatives. Scalable Bloom Filters place a tight upper bound on false positives while avoiding false negatives but require allocating memory proportional to the size of the data set. Counting Bloom Filters and Cuckoo Filters are useful for cases which require adding and removing elements to and from a set.
9
10For large or unbounded data sets, calculating the exact cardinality is impractical. HyperLogLog uses a fraction of the memory while providing an accurate approximation. Similarly, Count-Min Sketch provides an efficient way to estimate event frequency for data streams, while Top-K tracks the top-k most frequent elements.
11
12MinHash is a probabilistic algorithm to approximate the similarity between two sets. This can be used to cluster or compare documents by splitting the corpus into a bag of words.
13
14## Installation
15
16```
17$ go get github.com/tylertreat/BoomFilters
18```
19
20## Stable Bloom Filter
21
22This is an implementation of Stable Bloom Filters as described by Deng and Rafiei in [Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters](http://webdocs.cs.ualberta.ca/~drafiei/papers/DupDet06Sigmod.pdf).
23
24A Stable Bloom Filter (SBF) continuously evicts stale information so that it has room for more recent elements. Like traditional Bloom filters, an SBF has a non-zero probability of false positives, which is controlled by several parameters. Unlike the classic Bloom filter, an SBF has a tight upper bound on the rate of false positives while introducing a non-zero rate of false negatives. The false-positive rate of a classic Bloom filter eventually reaches 1, after which all queries result in a false positive. The stable-point property of an SBF means the false-positive rate asymptotically approaches a configurable fixed constant. A classic Bloom filter is actually a special case of SBF where the eviction rate is zero and the cell size is one, so this provides support for them as well (in addition to bitset-based Bloom filters).
25
26Stable Bloom Filters are useful for cases where the size of the data set isn't known a priori and memory is bounded. For example, an SBF can be used to deduplicate events from an unbounded event stream with a specified upper bound on false positives and minimal false negatives.
27
28### Usage
29
30```go
31package main
32
33import (
34 "fmt"
35 "github.com/tylertreat/BoomFilters"
36)
37
38func main() {
39 sbf := boom.NewDefaultStableBloomFilter(10000, 0.01)
40 fmt.Println("stable point", sbf.StablePoint())
41
42 sbf.Add([]byte(`a`))
43 if sbf.Test([]byte(`a`)) {
44 fmt.Println("contains a")
45 }
46
47 if !sbf.TestAndAdd([]byte(`b`)) {
48 fmt.Println("doesn't contain b")
49 }
50
51 if sbf.Test([]byte(`b`)) {
52 fmt.Println("now it contains b!")
53 }
54
55 // Restore to initial state.
56 sbf.Reset()
57}
58```
59
60## Scalable Bloom Filter
61
62This is an implementation of a Scalable Bloom Filter as described by Almeida, Baquero, Preguica, and Hutchison in [Scalable Bloom Filters](http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf).
63
64A Scalable Bloom Filter (SBF) dynamically adapts to the size of the data set while enforcing a tight upper bound on the rate of false positives and a false-negative probability of zero. This works by adding Bloom filters with geometrically decreasing false-positive rates as filters become full. A tightening ratio, r, controls the filter growth. The compounded probability over the whole series converges to a target value, even accounting for an infinite series.
65
66Scalable Bloom Filters are useful for cases where the size of the data set isn't known a priori and memory constraints aren't of particular concern. For situations where memory is bounded, consider using Inverse or Stable Bloom Filters.
67
68The core parts of this implementation were originally written by Jian Zhen as discussed in [Benchmarking Bloom Filters and Hash Functions in Go](http://zhen.org/blog/benchmarking-bloom-filters-and-hash-functions-in-go/).
69
70### Usage
71
72```go
73package main
74
75import (
76 "fmt"
77 "github.com/tylertreat/BoomFilters"
78)
79
80func main() {
81 sbf := boom.NewDefaultScalableBloomFilter(0.01)
82
83 sbf.Add([]byte(`a`))
84 if sbf.Test([]byte(`a`)) {
85 fmt.Println("contains a")
86 }
87
88 if !sbf.TestAndAdd([]byte(`b`)) {
89 fmt.Println("doesn't contain b")
90 }
91
92 if sbf.Test([]byte(`b`)) {
93 fmt.Println("now it contains b!")
94 }
95
96 // Restore to initial state.
97 sbf.Reset()
98}
99```
100
101## Inverse Bloom Filter
102
103An Inverse Bloom Filter, or "the opposite of a Bloom filter", is a concurrent, probabilistic data structure used to test whether an item has been observed or not. This implementation, [originally described and written by Jeff Hodges](http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/), replaces the use of MD5 hashing with a non-cryptographic FNV-1 function.
104
105The Inverse Bloom Filter may report a false negative but can never report a false positive. That is, it may report that an item has not been seen when it actually has, but it will never report an item as seen which it hasn't come across. This behaves in a similar manner to a fixed-size hashmap which does not handle conflicts.
106
107This structure is particularly well-suited to streams in which duplicates are relatively close together. It uses a CAS-style approach, which makes it thread-safe.
108
109### Usage
110
111```go
112package main
113
114import (
115 "fmt"
116 "github.com/tylertreat/BoomFilters"
117)
118
119func main() {
120 ibf := boom.NewInverseBloomFilter(10000)
121
122 ibf.Add([]byte(`a`))
123 if ibf.Test([]byte(`a`)) {
124 fmt.Println("contains a")
125 }
126
127 if !ibf.TestAndAdd([]byte(`b`)) {
128 fmt.Println("doesn't contain b")
129 }
130
131 if ibf.Test([]byte(`b`)) {
132 fmt.Println("now it contains b!")
133 }
134}
135```
136
137## Counting Bloom Filter
138
139This is an implementation of a Counting Bloom Filter as described by Fan, Cao, Almeida, and Broder in [Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol](http://pages.cs.wisc.edu/~jussara/papers/00ton.pdf).
140
141A Counting Bloom Filter (CBF) provides a way to remove elements by using an array of n-bit buckets. When an element is added, the respective buckets are incremented. To remove an element, the respective buckets are decremented. A query checks that each of the respective buckets are non-zero. Because CBFs allow elements to be removed, they introduce a non-zero probability of false negatives in addition to the possibility of false positives.
142
143Counting Bloom Filters are useful for cases where elements are both added and removed from the data set. Since they use n-bit buckets, CBFs use roughly n-times more memory than traditional Bloom filters.
144
145See Deletable Bloom Filter for an alternative which avoids false negatives.
146
147### Usage
148
149```go
150package main
151
152import (
153 "fmt"
154 "github.com/tylertreat/BoomFilters"
155)
156
157func main() {
158 bf := boom.NewDefaultCountingBloomFilter(1000, 0.01)
159
160 bf.Add([]byte(`a`))
161 if bf.Test([]byte(`a`)) {
162 fmt.Println("contains a")
163 }
164
165 if !bf.TestAndAdd([]byte(`b`)) {
166 fmt.Println("doesn't contain b")
167 }
168
169 if bf.TestAndRemove([]byte(`b`)) {
170 fmt.Println("removed b")
171 }
172
173 // Restore to initial state.
174 bf.Reset()
175}
176```
177
178## Cuckoo Filter
179
180This is an implementation of a Cuckoo Filter as described by Andersen, Kaminsky, and Mitzenmacher in [Cuckoo Filter: Practically Better Than Bloom](http://www.pdl.cmu.edu/PDL-FTP/FS/cuckoo-conext2014.pdf). The Cuckoo Filter is similar to the Counting Bloom Filter in that it supports adding and removing elements, but it does so in a way that doesn't significantly degrade space and performance.
181
182It works by using a cuckoo hashing scheme for inserting items. Instead of storing the elements themselves, it stores their fingerprints which also allows for item removal without false negatives (if you don't attempt to remove an item not contained in the filter).
183
184For applications that store many items and target moderately low false-positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters.
185
186### Usage
187
188```go
189package main
190
191import (
192 "fmt"
193 "github.com/tylertreat/BoomFilters"
194)
195
196func main() {
197 cf := boom.NewCuckooFilter(1000, 0.01)
198
199 cf.Add([]byte(`a`))
200 if cf.Test([]byte(`a`)) {
201 fmt.Println("contains a")
202 }
203
204 if contains, _ := cf.TestAndAdd([]byte(`b`)); !contains {
205 fmt.Println("doesn't contain b")
206 }
207
208 if cf.TestAndRemove([]byte(`b`)) {
209 fmt.Println("removed b")
210 }
211
212 // Restore to initial state.
213 cf.Reset()
214}
215```
216
217## Classic Bloom Filter
218
219A classic Bloom filter is a special case of a Stable Bloom Filter whose eviction rate is zero and cell size is one. We call this special case an Unstable Bloom Filter. Because cells require more memory overhead, this package also provides two bitset-based Bloom filter variations. The first variation is the traditional implementation consisting of a single bit array. The second implementation is a partitioned approach which uniformly distributes the probability of false positives across all elements.
220
221Bloom filters have a limited capacity, depending on the configured size. Once all bits are set, the probability of a false positive is 1. However, traditional Bloom filters cannot return a false negative.
222
223A Bloom filter is ideal for cases where the data set is known a priori because the false-positive rate can be configured by the size and number of hash functions.
224
225### Usage
226
227```go
228package main
229
230import (
231 "fmt"
232 "github.com/tylertreat/BoomFilters"
233)
234
235func main() {
236 // We could also use boom.NewUnstableBloomFilter or boom.NewPartitionedBloomFilter.
237 bf := boom.NewBloomFilter(1000, 0.01)
238
239 bf.Add([]byte(`a`))
240 if bf.Test([]byte(`a`)) {
241 fmt.Println("contains a")
242 }
243
244 if !bf.TestAndAdd([]byte(`b`)) {
245 fmt.Println("doesn't contain b")
246 }
247
248 if bf.Test([]byte(`b`)) {
249 fmt.Println("now it contains b!")
250 }
251
252 // Restore to initial state.
253 bf.Reset()
254}
255```
256
257## Count-Min Sketch
258
259This is an implementation of a Count-Min Sketch as described by Cormode and Muthukrishnan in [An Improved Data Stream Summary: The Count-Min Sketch and its Applications](http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf).
260
261A Count-Min Sketch (CMS) is a probabilistic data structure which approximates the frequency of events in a data stream. Unlike a hash map, a CMS uses sub-linear space at the expense of a configurable error factor. Similar to Counting Bloom filters, items are hashed to a series of buckets, which increment a counter. The frequency of an item is estimated by taking the minimum of each of the item's respective counter values.
262
263Count-Min Sketches are useful for counting the frequency of events in massive data sets or unbounded streams online. In these situations, storing the entire data set or allocating counters for every event in memory is impractical. It may be possible for offline processing, but real-time processing requires fast, space-efficient solutions like the CMS. For approximating set cardinality, refer to the HyperLogLog.
264
265### Usage
266
267```go
268package main
269
270import (
271 "fmt"
272 "github.com/tylertreat/BoomFilters"
273)
274
275func main() {
276 cms := boom.NewCountMinSketch(0.001, 0.99)
277
278 cms.Add([]byte(`alice`)).Add([]byte(`bob`)).Add([]byte(`bob`)).Add([]byte(`frank`))
279 fmt.Println("frequency of alice", cms.Count([]byte(`alice`)))
280 fmt.Println("frequency of bob", cms.Count([]byte(`bob`)))
281 fmt.Println("frequency of frank", cms.Count([]byte(`frank`)))
282
283
284 // Serialization example
285 buf := new(bytes.Buffer)
286 n, err := cms.WriteDataTo(buf)
287 if err != nil {
288 fmt.Println(err, n)
289 }
290
291 // Restore to initial state.
292 cms.Reset()
293
294 newCMS := boom.NewCountMinSketch(0.001, 0.99)
295 n, err = newCMS.ReadDataFrom(buf)
296 if err != nil {
297 fmt.Println(err, n)
298 }
299
300 fmt.Println("frequency of frank", newCMS.Count([]byte(`frank`)))
301
302
303}
304```
305
306## Top-K
307
308Top-K uses a Count-Min Sketch and min-heap to track the top-k most frequent elements in a stream.
309
310### Usage
311
312```go
313package main
314
315import (
316 "fmt"
317 "github.com/tylertreat/BoomFilters"
318)
319
320func main() {
321 topk := boom.NewTopK(0.001, 0.99, 5)
322
323 topk.Add([]byte(`bob`)).Add([]byte(`bob`)).Add([]byte(`bob`))
324 topk.Add([]byte(`tyler`)).Add([]byte(`tyler`)).Add([]byte(`tyler`)).Add([]byte(`tyler`))
325 topk.Add([]byte(`fred`))
326 topk.Add([]byte(`alice`)).Add([]byte(`alice`)).Add([]byte(`alice`)).Add([]byte(`alice`))
327 topk.Add([]byte(`james`))
328 topk.Add([]byte(`fred`))
329 topk.Add([]byte(`sara`)).Add([]byte(`sara`))
330 topk.Add([]byte(`bill`))
331
332 for i, element := range topk.Elements() {
333 fmt.Println(i, string(element.Data), element.Freq)
334 }
335
336 // Restore to initial state.
337 topk.Reset()
338}
339```
340
341## HyperLogLog
342
343This is an implementation of HyperLogLog as described by Flajolet, Fusy, Gandouet, and Meunier in [HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm](http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf).
344
345HyperLogLog is a probabilistic algorithm which approximates the number of distinct elements in a multiset. It works by hashing values and calculating the maximum number of leading zeros in the binary representation of each hash. If the maximum number of leading zeros is n, the estimated number of distinct elements in the set is 2^n. To minimize variance, the multiset is split into a configurable number of registers, the maximum number of leading zeros is calculated in the numbers in each register, and a harmonic mean is used to combine the estimates.
346
347For large or unbounded data sets, calculating the exact cardinality is impractical. HyperLogLog uses a fraction of the memory while providing an accurate approximation.
348
349This implementation was [originally written by Eric Lesh](https://github.com/eclesh/hyperloglog). Some small changes and additions have been made, including a way to construct a HyperLogLog optimized for a particular relative accuracy and adding FNV hashing. For counting element frequency, refer to the Count-Min Sketch.
350
351### Usage
352
353```go
354package main
355
356import (
357 "fmt"
358 "github.com/tylertreat/BoomFilters"
359)
360
361func main() {
362 hll, err := boom.NewDefaultHyperLogLog(0.1)
363 if err != nil {
364 panic(err)
365 }
366
367 hll.Add([]byte(`alice`)).Add([]byte(`bob`)).Add([]byte(`bob`)).Add([]byte(`frank`))
368 fmt.Println("count", hll.Count())
369
370 // Serialization example
371 buf := new(bytes.Buffer)
372 _, err = hll.WriteDataTo(buf)
373 if err != nil {
374 fmt.Println(err)
375 }
376
377 // Restore to initial state.
378 hll.Reset()
379
380 newHll, err := boom.NewDefaultHyperLogLog(0.1)
381 if err != nil {
382 fmt.Println(err)
383 }
384
385 _, err = newHll.ReadDataFrom(buf)
386 if err != nil {
387 fmt.Println(err)
388 }
389 fmt.Println("count", newHll.Count())
390
391}
392```
393
394## MinHash
395
396This is a variation of the technique for estimating similarity between two sets as presented by Broder in [On the resemblance and containment of documents](http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf).
397
398MinHash is a probabilistic algorithm which can be used to cluster or compare documents by splitting the corpus into a bag of words. MinHash returns the approximated similarity ratio of the two bags. The similarity is less accurate for very small bags of words.
399
400### Usage
401
402```go
403package main
404
405import (
406 "fmt"
407 "github.com/tylertreat/BoomFilters"
408)
409
410func main() {
411 bag1 := []string{"bill", "alice", "frank", "bob", "sara", "tyler", "james"}
412 bag2 := []string{"bill", "alice", "frank", "bob", "sara"}
413
414 fmt.Println("similarity", boom.MinHash(bag1, bag2))
415}
416```
417
418## References
419
420- [Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters](http://webdocs.cs.ualberta.ca/~drafiei/papers/DupDet06Sigmod.pdf)
421- [Scalable Bloom Filters](http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf)
422- [The Opposite of a Bloom Filter](http://www.somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter/)
423- [Benchmarking Bloom Filters and Hash Functions in Go](http://zhen.org/blog/benchmarking-bloom-filters-and-hash-functions-in-go/)
424- [Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol](http://pages.cs.wisc.edu/~jussara/papers/00ton.pdf)
425- [An Improved Data Stream Summary: The Count-Min Sketch and its Applications](http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf)
426- [HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm](http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)
427- [Package hyperloglog](https://github.com/eclesh/hyperloglog)
428- [On the resemblance and containment of documents](http://gatekeeper.dec.com/ftp/pub/dec/SRC/publications/broder/positano-final-wpnums.pdf)
429- [Cuckoo Filter: Practically Better Than Bloom](http://www.pdl.cmu.edu/PDL-FTP/FS/cuckoo-conext2014.pdf)
430