This chapter covers
- Describing and analyzing Bloom filters
- Keeping track of large documents using little memory
- Showing why dictionaries are an imperfect solution
- Improving the memory print by using Bloom filters
- Recognizing use cases where Bloom filters improve performance
- Using metrics to tune the quality of Bloom filters’ solutions
Starting with this chapter we’ll be reviewing less common data structures that solve, as strange as it might seem, common problems. Bloom filters are one of the most prominent examples; they are widely used in most industries, but not as widely known as you would expect for such a cornerstone.
In section 4.1 we introduce the problem that will be our North Star in this chapter: we need to keep track of large entities with the smallest memory print possible.
In section 4.2 we continue our narration by discussing a few increasingly complex solutions, showing their strengths and weaknesses; the latter, in particular, ought to be considered chances for improvement and fertile ground for algorithms designers.