| 1 |
Source: golang-github-willf-bloom |
| 2 |
Section: golang |
| 3 |
Priority: optional |
| 4 |
Maintainer: Debian Go Packaging Team <[email protected]> |
| 5 |
Uploaders: Thorsten Alteholz <[email protected]>, John Goerzen <[email protected]> |
| 6 |
Build-Depends: debhelper-compat (= 13), |
| 7 |
dh-golang, |
| 8 |
golang-any, |
| 9 |
golang-github-bits-and-blooms-bitset-dev (>= 1.13.0) |
| 10 |
Standards-Version: 4.6.2 |
| 11 |
Homepage: https://github.com/willf/bloom |
| 12 |
Vcs-Browser: https://salsa.debian.org/go-team/packages/golang-github-willf-bloom |
| 13 |
Vcs-Git: https://salsa.debian.org/go-team/packages/golang-github-willf-bloom.git |
| 14 |
XS-Go-Import-Path: github.com/willf/bloom, github.com/bits-and-blooms/bloom |
| 15 |
Testsuite: autopkgtest-pkg-go |
| 16 |
Rules-Requires-Root: no |
| 17 |
|
| 18 |
Package: golang-github-willf-bloom-dev |
| 19 |
Architecture: all |
| 20 |
Depends: golang-github-bits-and-blooms-bitset-dev, |
| 21 |
${misc:Depends} |
| 22 |
Description: Go package implementing Bloom filters |
| 23 |
A Bloom filter is a representation of a set of n items, where the main |
| 24 |
requirement is to make membership queries; i.e., whether an item is a |
| 25 |
member of a set. |
| 26 |
. |
| 27 |
A Bloom filter has two parameters: m, a maximum size (typically a |
| 28 |
reasonably large multiple of the cardinality of the set to represent) |
| 29 |
and k, the number of hashing functions on elements of the set. (The |
| 30 |
actual hashing functions are important, too, but this is not a |
| 31 |
parameter for this implementation). A Bloom filter is backed by a BitSet |
| 32 |
(https://github.com/willf/bitset); a key is represented in the filter |
| 33 |
by setting the bits at each value of the hashing functions (modulo |
| 34 |
m). Set membership is done by testing whether the bits at each value of |
| 35 |
the hashing functions (again, modulo m) are set. If so, the item is in |
| 36 |
the set. If the item is actually in the set, a Bloom filter will never |
| 37 |
fail (the true positive rate is 1.0); but it is susceptible to false |
| 38 |
positives. The art is to choose k and m correctly. |
| 39 |
. |
| 40 |
In this implementation, the hashing functions used is murmurhash |
| 41 |
(github.com/spaolacci/murmur3), a non-cryptographic hashing function. |