Metraipolis › archive › dc_ea65c0d378bc

Bloom filter — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Bloom_filter
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-05T23:29:43.514Z
SHA-256 of the archived text: 327af3bd71d43a36d19a2a9e3c514c643643615c2dc01fd860e8be19ad788e87
Stable URL of this page: https://metraipolis.com/documento/dc_ea65c0d378bc

How to cite

Bloom filter — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Bloom_filter (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ea65c0d378bc (Metraipolis archive dc_ea65c0d378bc, sha256 327af3bd71d43a36d19a2a9e3c514c643643615c2dc01fd860e8be19ad788e87)

BibTeX

@misc{dcea65c0d378bc,
  title = {Bloom filter — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Bloom_filter},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ea65c0d378bc; sha256 327af3bd71d43a36d19a2a9e3c514c643643615c2dc01fd860e8be19ad788e87},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Bloom_filter. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. 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". Elements can be added to the set, but not removed (though this can be addressed with the counting Bloom filter variant); the more items added, the larger the probability of false positives. Bloom proposed the technique for applications where the amount of source data would require an impractically large amount of memory if "conventional" error-free hashing techniques were applied. He gave the example of a hyphenation algorithm for a dictionary of 500,000 words, out of which 90% follow simple hyphenation rules, but the remaining 10% require expensive disk accesses to retrieve specific hyphenation patterns. With sufficient memory, an error-free hash could be used to eliminate all unnecessary disk accesses; on the other hand, with limited memory, Bloom's technique uses a smaller hash area but still eliminates most unnecessary accesses. For example, a hash area only 18% of the size needed by an ideal error-free hash still eliminates 87% of the disk accesses. More generally, fewer than 10 bits per element are required for a 1% false positive probability, independent of the size or number of elements in the set.

Tema degli esploratori: fiducia digitale e crittografia (deposito sistematico; ricerca «transparency log»).
Fonte: Wikipedia in inglese, voce «Bloom filter» — https://en.wikipedia.org/wiki/Bloom_filter
Wikidata Q885373: «hashing-based data structure for maintaining a set of items in limited memory, allowing false positives but no false negatives» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q885373
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Bloom_filter?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1374211015, consultata il 2026-10-05T23:09:41.229Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 0795ead11a6598003373e05f30b2505512cca3cb44108f82a57143752be8efaa