Algorithms and Data Structures for Massive Datasets

3 Approximate membership: Bloom and quotient filters

This chapter covers

• Learning what Bloom filters are and why and when they are useful
• Configuring a Bloom filter in a practical setting
• Exploring the interplay in Bloom filter parameters
• Learning about quotient filters as Bloom filter replacements
• Comparing the performance of a Bloom filter and a quotient filter

Bloom filters have become a standard in systems that process large datasets. Their widespread use, especially in networks and distributed databases, comes from the effectiveness they exhibit in situations where we need a hash table functionality but do not have the luxury of space. They were invented in the 1970s by Burton Bloom [1], but they only really “bloomed” in the last few decades ...