Binary Fuse Filters

Binary fuse filters for space-efficient probabilistic set membership testing in JavaScript and TypeScript. Binary fuse filters are similar to Bloom filters but use less space: approximately 9 bits per element (fuse8) compared to 10+ bits for a Bloom filter at the same false-positive rate.

This is a pure JavaScript implementation with no dependencies or platform-specific APIs, so it works in any JS environment including Node.js, browsers, and edge runtimes.

Ported from the C reference implementation, xor_singleheader, by Thomas Mueller Graf and Daniel Lemire.

Usage

import {
  createBinaryFuseFilter,
  binaryFuseFilterContains,
  serializeBinaryFuseFilter,
  deserializeBinaryFuseFilter,
} from '@expo/binary-fuse-filter';

// Build a filter from a set of strings
const filter = createBinaryFuseFilter(['alpha', 'bravo', 'charlie']);

// Test membership (no false negatives; rare false positives)
binaryFuseFilterContains(filter, 'alpha');   // true
binaryFuseFilterContains(filter, 'delta');   // false (probably)

// Serialize to bytes for storage or transfer, and deserialize later
const bytes = serializeBinaryFuseFilter(filter);
const restored = deserializeBinaryFuseFilter(bytes);

Fingerprint widths

The fingerprintBits parameter (second argument to createBinaryFuseFilter) controls the trade-off between false-positive rate and space:

| Width | False-positive rate | Bits per element | | ----- | ------------------- | ---------------- | | 8 | ~0.4% | ~9 | | 16 | ~0.002% | ~18 | | 32 | ~0.00000002% | ~34 |

The default is 8-bit fingerprints.

Credits

The binary fuse filter algorithm was developed by Thomas Mueller Graf and Daniel Lemire. The C reference implementation is available at FastFilter/xor_singleheader and licensed under the Apache License 2.0.

License

MIT (this library) and Apache 2.0 (original C implementation).