2004/01/01 by Andrei Broder, Michael Mitzenmacher · 10 citations
Computer Science · Materials Science · Mathematics · #Caching and Content Delivery #Covalent Organic Framework Applications #Network Packet Processing and Optimization #Bloom filter #Set (abstract data type) #Bloom #False positive paradox #Filter (signal processing) #Space (punctuation) #Mathematics #Variety (cybernetics) #Computer science #Data structure #Data mining #Theoretical computer science #Algorithm #Statistics #Programming language
paper · pdf · doi:10.1080/15427951.2004.10129096
openalex publication_date 2004/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters allow false positives but the space savings often outweigh this drawback when the probability of an error is controlled. Bloom filters have been used in database applications since the 1970s, but only in recent years have they become popular in the networking literature. The aim of this paper is to survey the ways in which Bloom filters have been used and modified in a variety of network problems, with the aim of providing a unified mathematical and practical framework for understanding them and stimulating their use in future applications.