Reminder: This post contains 463 words
· 2 min read
· by Xianbin
This paper [1] is cited by over 10000 papers! Amazing!
The bloom filter is used to answer an element \(x\in X\) or not. The answer is
The basic idea is as follows.
We use independent and uniformly distributed hash functions to map each element into a location with some indexes. When we query an element’s index, if all indexes are “1”, then we think this element maybe exist. Otherwise, it does not exist.
Reference
[1]. Bloom, Burton H. “Space/time trade-offs in hash coding with allowable errors.” Communications of the ACM 13.7 (1970): 422-426.