Genbox.FastFilter 1.0.0-alpha.1

FastFilter

Description

FastFilter is a C# implementation of a few different Bloom filters with focus on high performance. It contains the following Bloom filter implementations:

• Bloom filter
• Register Blocked Bloom filter
• BinaryFuse filter

Features

• Add()
• Contains()

Example

static void Main()
{
    int[] data = [1, 42, 30, 481, 58];
    BinaryFuse8Filter<int> fuse = new BinaryFuse8Filter<int>(data);

    Console.WriteLine("Does it contain 42? " + (fuse.Contains(42) ? "Maybe" : "No"));
    Console.WriteLine("Does it contain 50? " + (fuse.Contains(50) ? "Maybe" : "No"));
}

Output:

Does it contain 42? Maybe
Does it contain 50? No

The reason it says "Maybe" is because Bloom filters can have false positives, but never false negatives. If it says "No", it is guaranteed that the item is not in the filter.

Benchmarks

HashSetBloomFilter is a Bloom filter that uses a HashSet as a backing store. It is only included for comparison, since .NET does not natively have a Bloom filter. BinaryFuse filters give NA for Add() because they are immutable once constructed.

For retaining 1000 64bit integers (8000 bytes), the memory usage is as follows:

It is possible to tweak the false positive percentage for BloomFilter and BlockedBloomFilter. Lower false positive percent means more memory usage.