binary-fuse-filter · shipping · also binary fuse membership filter

Binary fuse filter

A binary fuse filter is a static approximate-membership structure that assigns XOR-linked fingerprints across consecutive segments to support compact membership tests.

Related Observatory article: Binary fuse filter on hesela.com

The original study considers three- and four-location variants; construction needs the complete set. Smaller storage does not imply lower construction memory or database latency. [1] The pinned C library assumes distinct 64-bit inputs and matching byte order for serialization; those are implementation conditions, not universal file-format guarantees. [2]

Relations

related
xor-filter, bloom-filter, ribbon-filter, sstable

Citations

  1. Graf and Lemire. Binary Fuse Filters: Fast and Smaller Than Xor Filters. ACM JEA 27 (2022). DOI: 10.1145/3510449. (accessed 2026-10-16)
  2. FastFilter xor_singleheader README, commit 5b6b321aa5c0c8ef5b5fb3145206f07f3754a0a1: input contract, construction memory and serialization. (accessed 2026-10-16)

Further reading

  1. Hesela. Static filters and reproducible fixed-equation examples. (accessed 2026-10-16)

JSON: /data/terms/binary-fuse-filter.json