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, first paragraphQuote, Lead section, first paragraph
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".
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.