BinaryFuseFilter 1.0.0

BinaryFuseFilter

Binary fuse filters (Graf and Lemire, 2022) for .NET. Build a filter once from a set of keys and it will answer "is this key possibly in the set?" with no false negatives and a small, tunable false-positive rate. Space cost is about 9 bits per key, roughly 25% below a Bloom filter of equal accuracy, and a query costs three memory reads where a Bloom filter needs eight or more. The catch is that filters are immutable, so keys cannot be added after construction. Pure managed C# with no native dependencies, targeting netstandard2.0 through net10.0.

Install

dotnet add package BinaryFuseFilter

Quick start

Pre-hashed core API (you bring 64-bit keys):

using BinaryFuse;

ulong[] keys = LoadKeyHashes();
var filter = BinaryFuse8Filter.Create(keys);

filter.Contains(keys[0]);      // true (never a false negative)
filter.Contains(12345);        // false, or true with ~0.39% probability

Generic API with built-in hashing (string, byte[], Guid, char and integer types; plug an IKeyHasher<T> for anything else):

var urls = new[] { "https://a.example", "https://b.example" };
var filter = BinaryFuseFilter<string>.Create(urls);
filter.Contains("https://a.example");   // true

Serialization round trip (compact binary, versioned header):

byte[] data = filter.Serialize();
// ... store or ship the bytes ...
var restored = BinaryFuseFilter.Deserialize(data);      // width read from the header
var typed = BinaryFuse8Filter.Deserialize(data);        // when you know the width

Batch queries write one answer per key. They run at the same speed as a plain loop over Contains, so use whichever form fits the surrounding code:

var results = new bool[keys.Length];
filter.Contains(keys, results);

Choosing a variant

All three share one construction algorithm; pick by how expensive a false positive is for you. A FrozenSet<ulong> of one million keys needs 64+ bits per key just for the values; BinaryFuse8Filter answers the same "definitely not present" question in about 9 bits per key.

Semantics

A filter is built once with Create and never changes afterwards. Queries are thread-safe and never throw. Every key that went into Create is found; duplicates in the input are removed internally, and KeyCount reports distinct keys. An empty input still gives a working filter, one that answers false for everything. The input array is never modified. Construction is also deterministic: the same keys on the same library version serialize to identical bytes.

Serialization format

A 32-byte little-endian header (magic, format version, fingerprint width, seed, segment geometry, key count) followed by the raw fingerprints. Loading validates every field and relationship before touching memory, and fails with InvalidDataException describing the problem. The version byte makes the format evolvable; within a released version the layout is a compatibility contract.

BinaryFuseFilter.Deserialize(data) reads the width from the header when you do not know it; BinaryFuse8Filter.Deserialize(data) insists on 8-bit data.

For BinaryFuseFilter<T> only the core filter is serialized: deserialize with the same hasher you built with (the same built-in default, or your same custom hasher), otherwise answers are silently wrong.

Performance

The construction algorithm is a faithful port of the canonical FastFilter xorfilter code. The query path is branch-free and bounds-check-free: three memory loads per lookup. Queries and construction allocate nothing beyond the filter itself.

Time ratios against BinaryFuse8Filter from one BenchmarkDotNet run on .NET 10 x64, lower is better. Reproduce with dotnet run -c Release --project src/BinaryFuseFilter.Benchmarks.

Query latency, mixed hit/miss lookups against filters built from 1M keys:

Construction from 1M pre-hashed keys:

License

MIT