Wrapping Up

Bloom filters can be used to save space even in instances where bit vectors cannot. A bit vector is generally limited to cases where our data is integers within a small range, but Bloom filters do not have these limitations. To keep themselves small, Bloom filters use the Monte Carlo approach—they sacrifice some accuracy in order to save space.

You’ve seen in previous chapters how Monte Carlo algorithms can also be used to gain speed. In short, then, the idea of Monte Carlo is to sacrifice some accuracy to gain either time or space.

In some cases, you may save both time and space. One example of this is using a Bloom filter to reduce database lookups (as described in ). The main purpose of maintaining a set in main memory in this context is to save time. And by specifically using a Bloom filter to serve as the set, you’re ensuring that your set takes up minimal space.