bloom-filter

    bloom filter

    bloom
    murmur
    hash
    bitvector
    Download zip
    Version
    0.1.5
    License
    MIT
    Last updated
    2 days ago
    Downloads
    47

    No dependencies

    #Bloom Filter

    This bloom filter library inspired by Go's bloom package.

    A bloom filter is a concise/compressed representation of a set, where the main requirement is to make membership queries; i.e., whether an item is a member of a set. A Bloom filter will always correctly report the presence of an element in the set when the element is indeed present. A Bloom filter can use much less storage than the original set, but it allows for some 'false positives': it may sometimes report that an element is in the set whereas it is not.

    When you construct, you need to know how many elements you have (the desired capacity), and what is the desired false positive rate you are willing to tolerate. A common false-positive rate is 1%. The lower the false-positive rate, the more memory you are going to require. Similarly, the higher the capacity, the more memory you will use. You may construct the Bloom filter capable of receiving 1 million elements with a false-positive rate of 1% in the following manner.

    let filter = new_with_estimates(1000000, 0.01)
    You should call new_with_estimates conservatively: if you specify a number of elements that it is too small, the false-positive bound might be exceeded. A Bloom filter is not a dynamic data structure: you must know ahead of time what your desired capacity is.

    Our implementation accepts keys for setting and testing as Bytes or String. Thus, to add a string item, "Hello":

    filter.add_string("Hello")

    To check if "Hello" is in bloom:

    filter.check_string("Hello")

    add_string / check_string hash the UTF-8 encoding of the string, so the same text always produces the same bits.

    For numerical data, hash the raw bytes of the value:

    let buf = Buffer()
    buf.write_int_le(100)
    let key = buf.to_bytes()
    filter.add(key)
    filter.check(key)

    #API at a glance

    // construction
    pub fn new_with_estimates(n : Int32, fp : Double) -> BloomFilter
    pub fn BloomFilter::new(m : Int32, k : Int32) -> BloomFilter
    pub fn BloomFilter::from(data : Array[UInt64], k : Int32) -> BloomFilter

    // membership
    pub fn BloomFilter::add(self : BloomFilter, data : Bytes) -> BloomFilter
    pub fn BloomFilter::add_string(self : BloomFilter, data : String) -> BloomFilter
    pub fn BloomFilter::check(self : BloomFilter, data : Bytes) -> Bool
    pub fn BloomFilter::check_string(self : BloomFilter, data : String) -> Bool
    pub fn BloomFilter::check_and_add(self : BloomFilter, data : Bytes) -> Bool
    pub fn BloomFilter::check_or_add(self : BloomFilter, data : Bytes) -> Bool

    // maintenance
    pub fn BloomFilter::merge(self : BloomFilter, other : BloomFilter) -> BloomFilter raise
    pub fn BloomFilter::copy(self : BloomFilter) -> BloomFilter raise
    pub fn BloomFilter::clear_all(self : BloomFilter) -> BloomFilter
    pub fn BloomFilter::equal(self : BloomFilter, other : BloomFilter) -> Bool
    pub fn BloomFilter::approximated_size(self : BloomFilter) -> Int32

    // serialization
    pub fn BloomFilter::marshal_bytes(self : BloomFilter) -> Bytes
    pub fn BloomFilter::unmarshal_bytes(bytes : Bytes) -> BloomFilter

    This library uses Int32 for sizes and counts (bit counts, hash-function counts, key lengths).

    #Installation

    Add chaijie2018/bloom to your dependencies:
    moon update moon add chaijie2018/bloom-filter

    #Verifying the False Positive Rate

    Sometimes, the actual false positive rate may differ (slightly) from the theoretical false positive rate. We have a function to estimate the false positive rate of a Bloom filter with m bits and k hashing functions for a set of size n:

    let n = 1000000 // expected number of items
    let fp = 0.01 // tolerated false-positive rate

    // For a filter of 20n bits with 5 hash functions the empirical rate should
    // stay around 0.1%:
    let rate = estimate_false_positive_rate(20 * n, 5, n)
    if rate > 0.001 {
    println("higher than expected: \{rate}")
    }

    You can use it to validate the computed m, k parameters:

    let (m, k) = estimate_parameters(n, fp)
    let actual_fp_rate = estimate_false_positive_rate(m, k, n)

    or

    let filter = new_with_estimates(n, fp)
    let actual_fp_rate = estimate_false_positive_rate(
    filter.get_cap(),
    filter.get_k(),
    n,
    )

    You would expect actual_fp_rate to be close to the desired false-positive rate fp in these cases.

    The estimate_false_positive_rate function creates a temporary Bloom filter. It is also relatively expensive and only meant for validation.

    #Design

    A Bloom filter has two parameters: m, the number of bits used in storage, and k, the number of hashing functions on elements of the set. (The actual hashing functions are important, too, but this is not a parameter for this implementation). A Bloom filter is backed by a BitVector; a key is represented in the filter by setting the bits at each value of the hashing functions (modulo m). Set membership is done by checking whether the bits at each value of the hashing functions (again, modulo m) are set. If so, the item is in the set. If the item is actually in the set, a Bloom filter will never fail (the true positive rate is 1.0); but it is susceptible to false positives. The art is to choose k and m correctly.

    In this implementation, the hashing functions used is murmurhash, a non-cryptographic hashing function.

    Given the particular hashing scheme, it's best to be empirical about this. Note that estimating the false positive rate will clear the Bloom filter.

    #Development

    The library targets the current MoonBit toolchain and uses the moon.mod / moon.pkg manifests. There are no third-party dependencies: the only imports are moonbitlang/core packages (encoding/utf8, math) plus the bundled internal/bitvec package.

    moon check # type-check moon test # run the test suite moon fmt # format moon info # refresh the .mbti interface files

    #Contributing

    If you wish to contribute to this project, please branch and issue a pull request against master ("bloom-filter")

    BitVector

    BitVector is an immutable bit vector data structure for compact and efficient storage and manipulation of boolean sequences. It provides a series of bit operations while maintaining immutability (all modification operations return new BitVector instances).

    BloomFilter

    pub struct BloomFilter {
    m : Int
    k : Int
    b :
    BitVector

    }

    A BloomFilter is a representation of a set of n items, where the main requirement is to make membership queries; i.e., whether an item is a member of a set.

    BloomFilter::add

    fn BloomFilter::add(self : BloomFilter, data : Bytes) -> BloomFilter

    Add data to the Bloom Filter. Returns the filter (allows chaining)

    BloomFilter::add_string

    fn BloomFilter::add_string(self : BloomFilter, data : String) -> BloomFilter

    Returns the filter (allows chaining)

    BloomFilter::approximated_size

    fn BloomFilter::approximated_size(self : BloomFilter) -> Int

    Approximating the number of items https://en.wikipedia.org/wiki/Bloom_filter#Approximating_the_number_of_items_in_a_Bloom_filter

    BloomFilter::check

    fn BloomFilter::check(self : BloomFilter, data : Bytes) -> Bool

    Return true if the data is in the BloomFilter, false otherwise. If true, the result might be a false positive. If false, the data is definitely not in the set.

    BloomFilter::check_and_add

    fn BloomFilter::check_and_add(self : BloomFilter, data : Bytes) -> Bool

    The filter is written to unconditionnally: even if the element is present, the corresponding bits are still set.

    BloomFilter::check_and_add_string

    fn BloomFilter::check_and_add_string(self : BloomFilter, data : String) -> Bool

    The filter is written to unconditionnally: even if the string is present, the corresponding bits are still set.

    BloomFilter::check_locations

    fn BloomFilter::check_locations(self : BloomFilter, locs : Array[Int]) -> Bool

    check_locations returns true if all locations are set in the BloomFilter, false otherwise.

    BloomFilter::check_or_add

    fn BloomFilter::check_or_add(self : BloomFilter, data : Bytes) -> Bool

    If the element is already in the filter, then the filter is unchanged.

    BloomFilter::check_or_add_string

    fn BloomFilter::check_or_add_string(self : BloomFilter, data : String) -> Bool

    If the string is already in the filter, then the filter is unchanged. Returns the result of check.

    BloomFilter::check_string

    fn BloomFilter::check_string(self : BloomFilter, data : String) -> Bool

    check_string returns true if the string is in the BloomFilter, false otherwise. If true, the result might be a false positive. If false, the data is definitely not in the set.

    BloomFilter::clear_all

    fn BloomFilter::clear_all(self : BloomFilter) -> BloomFilter

    Clears all the data in a Bloom filter, removing all keys

    BloomFilter::copy

    fn BloomFilter::copy(self : BloomFilter) -> BloomFilter raise

    Copy creates a copy of a Bloom filter.

    BloomFilter::equal

    fn BloomFilter::equal(self : BloomFilter, other : BloomFilter) -> Bool

    Equal tests for the equality of two Bloom filters

    BloomFilter::from

    fn BloomFilter::from(data : Array[UInt64], k : Int) -> BloomFilter

    From creates a new Bloom filter with data.length() * 64 bits and k hashing functions. The data slice is not going to be reset.

    BloomFilter::from_with_m

    fn BloomFilter::from_with_m(data : Array[UInt64], m : Int, k : Int) -> BloomFilter

    from_with_m creates a new Bloom filter with m length, k hashing functions. The data slice is not going to be reset.

    BloomFilter::get_bitvec

    Return the underlying bitset for this BloomFilter

    BloomFilter::get_cap

    fn BloomFilter::get_cap(self : BloomFilter) -> Int

    Returns the capacity, m, of a BloomFilter

    BloomFilter::get_k

    fn BloomFilter::get_k(self : BloomFilter) -> Int

    Returns the number of hash functions used in the BloomFilter

    BloomFilter::location

    fn BloomFilter::location(self : BloomFilter, hash256 : (UInt64, UInt64, UInt64, UInt64), i : Int) -> Int

    Return the ith hashed location using the four base hash values

    BloomFilter::marshal_bytes

    fn BloomFilter::marshal_bytes(self : BloomFilter) -> Bytes

    Serialize from BloomFilter to Bytes

    BloomFilter::merge

    fn BloomFilter::merge(self : BloomFilter, other : BloomFilter) -> BloomFilter raise

    Merge the data from two Bloom Filters.

    BloomFilter::new

    fn BloomFilter::new(m : Int, k : Int) -> BloomFilter

    New creates a new BloomFilter with m bits and k hashing functions. We force m and k to be at least one to avoid panics.

    BloomFilter::unmarshal_bytes

    fn BloomFilter::unmarshal_bytes(bytes : Bytes) -> BloomFilter

    Serialize from Bytes to BloomFilter

    base_hashes

    fn base_hashes(data : Bytes) -> (UInt64, UInt64, UInt64, UInt64)

    Return the four hash values of data that are used to create k hashes

    estimate_false_positive_rate

    fn estimate_false_positive_rate(m : Int, k : Int, n : Int) -> Double

    estimate_false_positive_rate returns, for a BloomFilter of m bits and k hash functions, an estimation of the false positive rate when storing n entries. This is an empirical, relatively slow test using integers as keys: each key is hashed as its 4-byte little-endian encoding. This function is useful to validate the implementation.

    estimate_parameters

    fn estimate_parameters(n : Int, fp : Double) -> (Int, Int)

    Estimate requirements for m and k.

    locations

    fn locations(data : Bytes, k : Int) -> Array[UInt64]

    locations returns a list of hash locations representing a data item.

    new_with_estimates

    fn new_with_estimates(n : Int, fp : Double) -> BloomFilter

    Create a new Bloom filter for n items with fp false positive rate