A space-efficient probabilistic structure that tests whether an element is possibly in a set or definitely not, trading a small false-positive rate for far less memory than storing the set outright; used to avoid expensive lookups such as a disk read or a network call.
Facts
Core PrincipleA space-efficient probabilistic data structure that tests whether an element is possibly a member of a set or definitely not a member; false positives are possible but false negatives are not, trading a small false-positive rate for large memory savings. 1 Connections
Sources
1. Wikipedia: Bloom filter
Wikimedia FoundationLead section
False positive matches are possible, but false negatives are not - in other words, a query returns either "possibly in set" or "definitely not in set".
In Group: Hashing and Probabilistic Structures, Lead
In computing, a Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set.
View the Source Essays About This Entity (1 essay)
The Structure That Admits It Might Be Wrong
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.