Space/Time Trade-offs in Hash Coding with Allowable Errors.¶
Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13(7), 422-426.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Asymmetric Screening
- In computer science it is the Bloom filter and the Cuckoo filter — the canonical case, where false positives are allowed but false negatives are impossible by construction
This sourceIntroduces the Bloom filter, whose construction makes false negatives impossible while admitting tunable false positives — a provably one-sided-error cheap filter.
Supported in partVerified against the work's full text
Bloom's 1970 paper gives the original filter that tolerates false positives (errors of commission) while rejecting only true non-members; it predates and does not cover Cuckoo filters.
“It will be shown that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used”
- In computer science it is the Bloom filter and the Cuckoo filter — the canonical case, where false positives are allowed but false negatives are impossible by construction
Domain-specific¶
- Bloom Filter
- A Bloom filter, introduced by Burton Bloom (1970) for hyphenation-rule lookup, is a probabilistic data structure that answers set-membership queries using a compact bit array and a fixed number of independent hash functions, and does so with a specific, intentional error asymmetry: it may report false positives (asserting that an element is in the set when it is not) but it never reports false negatives (it never denies membership for an element that was actually inserted).
This sourceThe founding analysis of hash coding that trades a small, controlled fraction of false-positive (errors-of-commission) membership errors for a much smaller hash area.
Supported in partVerified against the publisher's abstract
“The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications”
- A Bloom filter, introduced by Burton Bloom (1970) for hyphenation-rule lookup, is a probabilistic data structure that answers set-membership queries using a compact bit array and a fixed number of independent hash functions, and does so with a specific, intentional error asymmetry: it may report false positives (asserting that an element is in the set when it is not) but it never reports false negatives (it never denies membership for an element that was actually inserted).
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 2 citations: 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:6466e13e291f · see in the full table