Network Applications of Bloom Filters¶
Broder, A., & Mitzenmacher, M. (2004). Network Applications of Bloom Filters: A Survey. Internet Mathematics, 1(4), 485-509.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Asymmetric Screening
- along with spam quarantine queues, branch prediction with rollback, hash-based deduplication front-ends, tiered cache lookups, and approximate-nearest-neighbour search before exact rerank.
This sourceSurveys Bloom-filter applications as cheap front-ends gating expensive lookups and gives the false-positive probability as a function of array size and hash count.
Supported in partVerified against the work's full text
Survey shows Bloom filters gating costlier database and web-cache lookups; it does not cover spam queues, branch prediction, dedup front-ends or approximate nearest-neighbour rerank.
“Instead of keeping a list of all records that have changed, one can keep a Bloom”
- along with spam quarantine queues, branch prediction with rollback, hash-based deduplication front-ends, tiered cache lookups, and approximate-nearest-neighbour search before exact rerank.
Domain-specific¶
- Bloom Filter
- The false-positive probability is determined by three parameters — m (bit array size), k (number of hash functions), and n (number of inserted items) — and can be made arbitrarily small by increasing m or tuning k for a given workload, at the cost of proportionally more memory.
This sourceThe space-accuracy analysis placing Bloom filters within a factor log2 e (about 1.44) of the information-theoretic lower bound, needing m >= n log2 e · log2(1/eps) bits for false-positive rate eps.
SupportedVerified against the work's full text
“of m bits, initially all set to 0. A Bloom filter uses k independent hash functions”
- The false-positive probability is determined by three parameters — m (bit array size), k (number of hash functions), and n (number of inserted items) — and can be made arbitrarily small by increasing m or tuning k for a given workload, at the cost of proportionally more memory.
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: 1 supported, 1 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:d12d458bf981 · see in the full table