Bloom Filters

May 01, 2025 at 18:35 Tags Go The original motivation for the creation of Bloom filters is efficient set membership, using a probabilistic approach to significantly reduce the time and space required to reject items that are not members in a certain set. The data structure was proposed by Burton Bloom in a 1970 paper titled "Space/Time Trade-offs in Hash Coding with Allowable Errors". It's a good paper that's worth reading. Why Bloom filters? Suppose that we store some information on disk and want to check if a certain file contains a certain entry. Reading from disk is time consuming, so we want to minimize it as much as possible. A Bloom filter is a data structure that implements a cache with probabilistic properties: If the cache says the key is not present in a specific file, then it's 100% certain we should not be reading the file. If the cache says the key is present in the file, there's a small chance this is a false positive (and in fact the key isn't there). In this case we ... Read full article.