4 Bloom filters: Reducing the memory for tracking content
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 ...
Get Advanced Algorithms and Data Structures now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
