Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Static XOR filters: peel a fingerprint membership index

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A static XOR filter answers approximate membership for an immutable key set. Each key hashes to three positions in separate slot groups; the XOR of the three stored fingerprints equals a short fingerprint of that key. Construction makes a three-uniform hypergraph of these positions, repeatedly removes degree-one positions, then assigns fingerprints in reverse peel order. A cycle that cannot be peeled causes a new hash seed and a complete rebuild. This example deduplicates IDs before construction, uses eight-bit fingerprints, partitions slots into three groups, and caps seed attempts. An inserted key has no false negative after successful construction; a nonmember can match by chance, so every positive still needs authoritative verification.

Operational case

An immutable alert snapshot contains IDs 19, 29, 47, 61, 83, and 103. The filter reports possible membership for 47, 61, and 83. It does not store payloads or prove the IDs still exist in a later snapshot. A dispatch service can use a negative answer to skip a more expensive exact lookup, but it must check the exact index after a positive. If an alert is added, changing one slot would corrupt other keys' equations; rebuild the filter from the new full set and publish it with the matching exact-index version. A failed peel attempt is a construction failure, not permission to publish a filter that might reject a present alert.

Working Python program

python
from collections import deque
from hashlib import blake2b


class StaticAlertXorFilter:
    def __init__(self, alert_ids):
        keys = sorted(set(alert_ids))
        self.block_size = max(2, (len(keys) * 3 + 3) // 4)
        self.slots = []
        self.seed = None
        if not keys:
            return
        for seed in range(1, 301):
            hashes = [self._hash(key, seed) for key in keys]
            if len(set(hashes)) != len(hashes):
                continue
            degree = [0] * (3 * self.block_size)
            neighbors = [0] * (3 * self.block_size)
            for hashed in hashes:
                for position in self._positions(hashed):
                    degree[position] += 1
                    neighbors[position] ^= hashed
            queue = deque(index for index, count in enumerate(degree) if count == 1)
            peel = []
            while queue:
                position = queue.popleft()
                if degree[position] != 1:
                    continue
                hashed = neighbors[position]
                peel.append((hashed, position))
                for neighbor in self._positions(hashed):
                    degree[neighbor] -= 1
                    neighbors[neighbor] ^= hashed
                    if degree[neighbor] == 1:
                        queue.append(neighbor)
            if len(peel) != len(keys):
                continue
            self.seed = seed
            self.slots = [0] * len(degree)
            for hashed, position in reversed(peel):
                fingerprint = self._fingerprint(hashed)
                for neighbor in self._positions(hashed):
                    if neighbor != position:
                        fingerprint ^= self.slots[neighbor]
                self.slots[position] = fingerprint
            assert all(self.possibly_contains(key) for key in keys)
            return
        raise RuntimeError("could not peel alert set within rebuild budget")

    @staticmethod
    def _hash(alert_id, seed):
        payload = f"{seed}:{alert_id}".encode("utf8")
        return int.from_bytes(blake2b(payload, digest_size=8).digest(), "little")

    def _positions(self, hashed):
        return tuple(group * self.block_size + ((hashed >> (group * 21)) % self.block_size)
                     for group in range(3))

    @staticmethod
    def _fingerprint(hashed):
        return (hashed ^ (hashed >> 32)) & 255

    def possibly_contains(self, alert_id):
        if self.seed is None:
            return False
        hashed = self._hash(alert_id, self.seed)
        combined = 0
        for position in self._positions(hashed):
            combined ^= self.slots[position]
        return combined == self._fingerprint(hashed)


filter_index = StaticAlertXorFilter([47, 19, 61, 83, 29, 103])
print([filter_index.possibly_contains(key) for key in [47, 61, 83]])
print(filter_index.seed, len(filter_index.slots))

Output

Output
[True, True, True]
1 15

Time, space, and tradeoff

With sufficient slots and favorable hashes, peeling and assignment are linear in N keys and slots; the bounded retry loop can multiply that work and can fail after its configured attempts. A query performs three slot reads and O(1) hash work. Conceptually, the eight-bit slot array occupies eight times the slot count bits, but this Python list of integers has much greater actual memory overhead. The chosen slot count is deliberately generous and no optimal-size or measured false-positive claim is made. Hash collisions among distinct stored IDs are rejected during construction. The structure is static: deletion, insertion, and synchronization with an exact index require rebuilding or a versioned overlay design.

Common Mistakes

  • Do not treat a positive answer as exact membership.
  • Do not publish a partially peeled filter after a failed seed.
  • Do not mutate a slot for one insertion without rebuilding.
  • Do not describe Python-list memory as packed fingerprint bytes.

Connected lessons

Compare its update and query contract with Two-dimensional range trees: count a static rectangle, Van Emde Boas trees: successor in a bounded integer universe, Scapegoat trees: rebuild a deep insertion subtree, then complete the structure audit and decision quiz.

Two-level perfect hashing: exact static case membership adds a distinct structure contract to compare.

data structures
range-query-structures
Storage details