# C1: Bloom Filter

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

- No
- Maybe

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.