2026-09-22T03:10:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26028 2026-09-05T19:35:00Z ddc:004 open_access

ZOR Filters: Fast and Smaller Than Fuse Filters Limasset, Antoine Data structure Approximate Set Membership Static filter Probabilistic membership filters support fast approximate membership queries with controlled false-positive probability ε and are widely used across storage, analytics, networking, and bioinformatics [Chang et al., 2008; Niv Dayan et al., 2018; Broder and Mitzenmacher, 2004; Harris and Medvedev, 2020; Marchet and Limasset, 2023; Chikhi et al., 2025; Hernandez-Courbevoie et al., 2025]. In the static setting, low-overhead methods such as XOR, Fuse, and BuRR have been proposed [Graf and Lemire, 2020; Graf and Lemire, 2022; Dillinger et al., 2022; Ulrich and Renard, 2023]. Among these, Fuse filters are known for near-optimal query throughput. For XOR/Fuse-style peeling constructions, however, build success is only high probability, which complicates deterministic builds. We introduce ZOR filters, a deterministic continuation of XOR/Fuse-style constructions that guarantees termination while preserving the same XOR-based query mechanism. ZOR replaces restart-on-failure with deterministic peeling that abandons a small fraction of keys, and restores false-positive-only semantics by storing the remainder in a compact auxiliary structure. In our experiments, the abandoned fraction drops below 1% for moderate arity (e.g., N ≥ 5), so the auxiliary handles a negligible fraction of keys. As a result, ZOR filters can be substantially more memory-efficient than Fuse filters, with overhead below 1%, while not yet matching the near-optimal overhead of BuRR (below 0.1%). In query performance, ZOR-pure is close to Fuse and faster than BuRR on positive queries, while the complete interleaved variant trades additional negative-query latency for deterministic continuation. Relative to optimised Fuse/BuRR implementations [Graf and Lemire, 2022; Dillinger et al., 2022], the current ZOR prototype remains slower in construction because deterministic peeling requires explicit incidence handling; reducing this construction gap is an important direction for future work. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antoine Limasset 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.24 urn:nbn:de:0030-drops-260281 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.24 eng https://creativecommons.org/licenses/by/4.0/legalcode