Package Usage: go: github.com/greatroar/blobloom
Package blobloom implements blocked Bloom filters.
Blocked Bloom filters are an approximate set data structure: if a key has
been added to a filter, a lookup of that key returns true, but if the key
has not been added, there is a non-zero probability that the lookup still
returns true (a false positive). False negatives are impossible: if the
lookup for a key returns false, that key has not been added.
In this package, keys are represented exclusively as hashes. Client code
is responsible for supplying a 64-bit hash value.
Compared to standard Bloom filters, blocked Bloom filters use the CPU
cache more efficiently. A blocked Bloom filter is an array of ordinary
Bloom filters of fixed size BlockBits (the blocks). The lower half of the
hash selects the block to use.
To achieve the same false positive rate (FPR) as a standard Bloom filter,
a blocked Bloom filter requires more memory. For an FPR of at most 2e-6
(two in a million), it uses ~20% more memory. At 1e-10, the space required
is double that of standard Bloom filter.
For more details, see the 2010 paper by Putze, Sanders and Singler,
https://algo2.iti.kit.edu/documents/cacheefficientbloomfilters-jea.pdf.
14 versions
Latest release: almost 3 years ago
14 dependent packages
View more package details: https://packages.ecosystem.code.gouv.fr/registries/proxy.golang.org/packages/github.com/greatroar/blobloom