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".
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.