The End of Bloom Filters? Meet the XOR Filter

Bloom filters have long been a standard tool for answering an important question efficiently: does this item probably belong to a set? They are compact, fast, and useful when the application can tolerate false positives. A Bloom filter may say that an item is present when it is not, but it must not say that an inserted item is absent.

The XOR filter addresses the same general problem with a different construction. Instead of updating several bits for every inserted key, it builds an array of small fingerprints. A query combines the values stored at several positions using XOR and compares the result with the queried key's fingerprint.

The interesting part is not only the query formula. The array must be constructed so that every inserted key receives the correct answer even though different keys share positions. That construction is based on a peeling algorithm. The peeling step temporarily turns a global assignment problem into a sequence of local decisions, and a reverse pass fills the final fingerprint array.

This article explains the central ideas using the six-slot, three-hash-function model described in the video. The goal is not to present a particular implementation, but to make the data structure's behavior, construction, and trade-offs intuitive.

What Problem Does an XOR Filter Solve?​

Suppose an application has a set of keys such as object identifiers, URLs, database records, or cache entries. It frequently receives a query key and wants a quick membership test.

The desired behavior is usually:

• An inserted key should always be reported as present.
• A key that was never inserted may occasionally be reported as present.
• The structure should use little memory.
• Queries should require only a small, predictable amount of work.

The second condition is the source of the term false positive. A false positive is not a bug in the probabilistic data structure; it is an accepted consequence of compressing membership information. The application must decide what to do after a positive result. For example, a positive result might trigger a more expensive lookup in an authoritative database, while a negative result can safely skip that lookup.

An XOR filter is therefore best understood as a compact, probabilistic membership filter. The title's question about the end of Bloom filters is deliberately provocative: XOR filters do not make Bloom filters universally obsolete. They offer a different space-and-speed trade-off and are useful when their construction model fits the workload.

The Basic Ingredients​

The simplified design uses three ingredients:

1. A set of keys to represent.
2. Three hash functions, or three hash-derived positions for each key.
3. An array of fingerprint values.

In the six-slot example, the fingerprint array has positions numbered from 0 through 5. For each key, the three hash functions choose three candidate positions. A key might map to positions 0, 2, and 5, while another key might map to positions 1, 2, and 4.

The key's fingerprint is a short value derived from the key. It is not the complete key. The filter stores only this compact fingerprint indirectly through the values placed in the array.

For an inserted key x, let its three positions be:

h1(x), h2(x), h3(x)

and let its fingerprint be:

f(x)

The construction tries to assign array values so that the following relationship holds for every inserted key:

A[h1(x)] XOR A[h2(x)] XOR A[h3(x)] = f(x)

Here, A is the fingerprint array and XOR is the bitwise exclusive-or operation.

This equation is the heart of an XOR filter. During a query, the filter recomputes the three positions and the query fingerprint, reads the three array entries, XORs them together, and compares the result with the fingerprint. Equality means the filter reports a positive result; inequality means it reports a negative result.

Why XOR Is Useful Here​

XOR has a particularly convenient property: if the same value is XORed twice, the two copies cancel.

v XOR v = 0

It also has an inverse-like behavior:

u XOR v XOR u = v

This makes it possible to solve for a missing array value. If a key requires:

A[p1] XOR A[p2] XOR A[p3] = f

and two of the array entries are already known, the remaining entry can be calculated as:

A[p3] = f XOR A[p1] XOR A[p2]

That calculation is what makes the reverse assignment phase possible. The construction does not need to choose all three values for a key at once. It can leave one position to be determined after the other positions have been considered.

This algebraic property is fundamental to the entire construction strategy. Without it, the peeling and reverse assignment approach would not work. The XOR operation's self-inverse nature transforms a complex global constraint problem into a sequence of local, solvable equations.

Why Construction Is Harder Than Querying​

Querying is simple once the array exists. Construction is more subtle because keys overlap.

Imagine two keys that both use slot 2. Changing A[2] affects the equation for both keys. If we assign values in an arbitrary order, a later assignment can invalidate an earlier key's result. The filter needs a careful order of assignments that avoids this conflict.

The construction represents the relationships between keys and positions as a graph-like structure. Each key is associated with three array positions. You can visualize a key as a three-way connection to its candidate slots. In a six-slot example, a key might connect to slots 0, 2, and 5.

The important question is: is there a key that currently has a position used by no other remaining key? If so, that key can be removed temporarily. The unique position gives us a place where the key's final equation can later be satisfied without competing with another remaining key.

Finding and repeatedly removing such keys is the peeling algorithm. This approach transforms the problem from "solve all equations simultaneously" to "find a safe removal order, then solve in reverse."

The Peeling Algorithm​

Peeling is a strategy for finding a safe order of keys.

At a high level, construction proceeds as follows:

1. Hash every key to its three candidate positions.
2. Count how many remaining keys touch each array position.
3. Find a key that has at least one position with the required uniqueness property.
4. Record that key and the position selected for it.
5. Remove the key from the temporary construction graph.
6. Update the counts of its three positions.
7. Continue until all keys have been removed or no removable key remains.

The word peeling is useful as an image: repeatedly strip away an easy outer piece until the structure has been reduced.

For a key with positions (p1, p2, p3), suppose p2 is currently unique among the remaining keys. The construction records that p2 will be the key's solving position. The key can then be removed from the graph, even though the actual array values have not necessarily been finalized yet.

The removal order matters. It creates a reverse order in which array entries can be assigned safely. The algorithm maintains a queue or stack of keys that have at least one unique position. When a key is removed, the positions it touched may become unique for other keys, adding them to the queue.

This greedy approach works because the XOR structure has a special property: once a key is assigned a solving position, that position's value can be computed independently of other keys' assignments, as long as the other two positions have already been determined.

A Small Six-Slot Illustration​

Consider an array with six positions:

A[0], A[1], A[2], A[3], A[4], A[5]

Suppose several keys have been mapped to triples of positions:

Key P: (0, 2, 5)
Key Q: (1, 2, 4)
Key R: (3, 4, 5)

This is only an illustrative arrangement. The actual positions would come from hash functions.

Initially, count the usage of each position:

Position 0: used by P (count = 1)
Position 1: used by Q (count = 1)
Position 2: used by P, Q (count = 2)
Position 3: used by R (count = 1)
Position 4: used by Q, R (count = 2)
Position 5: used by P, R (count = 2)

Positions 0, 1, and 3 each have count 1, meaning they are unique to a single key. The algorithm can choose any of these. Suppose it selects position 0 for key P. It records:

(P, solving position 0)

and removes P from the graph. After removal, update the counts:

Position 0: count = 0 (removed)
Position 1: used by Q (count = 1)
Position 2: used by Q (count = 1)
Position 3: used by R (count = 1)
Position 4: used by Q, R (count = 2)
Position 5: used by R (count = 1)

Now positions 1, 2, 3, and 5 all have count 1. The algorithm can select any of them. Suppose it chooses position 1 for key Q:

(Q, solving position 1)

Remove Q and update counts:

Position 0: count = 0
Position 1: count = 0 (removed)
Position 2: count = 0 (removed)
Position 3: used by R (count = 1)
Position 4: used by R (count = 1)
Position 5: used by R (count = 1)

Key R now has all three positions unique. Select any one, say position 3:

(R, solving position 3)

Remove R. All keys have been peeled. The recorded sequence is:

(P, 0)
(Q, 1)
(R, 3)

This sequence will be reversed during the assignment phase.

The Reverse Assignment Phase​

Once peeling has removed all keys, the construction has an ordered list of decisions. It now processes that list backward.

For each recorded key, the algorithm knows:

• The key's three candidate positions.
• The key's fingerprint.
• Which one of the three positions was selected as its solving position.

Processing the list in reverse order: (R, 3), (Q, 1), (P, 0).

Step 1: Assign R

Key R has positions (3, 4, 5) and solving position 3. Its fingerprint is f(R). The equation is:

A[3] XOR A[4] XOR A[5] = f(R)

At this point, A[4] and A[5] have not been assigned yet. Initialize them to 0 (or any default value). Then:

A[3] = f(R) XOR A[4] XOR A[5] = f(R) XOR 0 XOR 0 = f(R)

So A[3] = f(R).

Step 2: Assign Q

Key Q has positions (1, 2, 4) and solving position 1. Its fingerprint is f(Q). The equation is:

A[1] XOR A[2] XOR A[4] = f(Q)

Positions 2 and 4 have not been assigned yet. Initialize them to 0. Then:

A[1] = f(Q) XOR A[2] XOR A[4] = f(Q) XOR 0 XOR 0 = f(Q)

So A[1] = f(Q).

Step 3: Assign P

Key P has positions (0, 2, 5) and solving position 0. Its fingerprint is f(P). The equation is:

A[0] XOR A[2] XOR A[5] = f(P)

Positions 2 and 5 have not been assigned yet. Initialize them to 0. Then:

A[0] = f(P) XOR A[2] XOR A[5] = f(P) XOR 0 XOR 0 = f(P)

So A[0] = f(P).

After this phase, the array is:

A[0] = f(P)
A[1] = f(Q)
A[2] = 0
A[3] = f(R)
A[4] = 0
A[5] = 0

Verify the equations:

• P: A[0] XOR A[2] XOR A[5] = f(P) XOR 0 XOR 0 = f(P) ✓
• Q: A[1] XOR A[2] XOR A[4] = f(Q) XOR 0 XOR 0 = f(Q) ✓
• R: A[3] XOR A[4] XOR A[5] = f(R) XOR 0 XOR 0 = f(R) ✓

This simplified example shows the core idea. In a real scenario with more keys and more complex overlaps, the unassigned positions would receive values from other keys' assignments, and the XOR cancellation property would ensure consistency.

The reverse order is essential. Peeling identified a position that was safe when the key was removed. Reversing the removal order ensures that the corresponding assignment can be made without breaking the constraints that have already been established in the reverse process.

This two-phase design is a common algorithmic pattern:

• A forward phase discovers a dependency order.
• A backward phase uses that order to compute values.

The peeling phase is about structure and ordering. The reverse phase is about arithmetic over XOR.

What If Peeling Gets Stuck?​

Peeling can reach a state in which every remaining key is entangled with the others: no remaining key has a suitable unique position. In graph terms, the remaining component contains a cycle-like dependency that cannot be removed using the simple local rule.

For example, suppose three keys remain:

Key X: (0, 1, 2)
Key Y: (1, 2, 3)
Key Z: (0, 2, 3)

Position counts:

Position 0: X, Z (count = 2)
Position 1: X, Y (count = 2)
Position 2: X, Y, Z (count = 3)
Position 3: Y, Z (count = 2)

Every position is shared by at least two keys. No key has a unique position. The peeling algorithm cannot proceed.

A practical construction must account for this possibility. A typical strategy is to try a different hash arrangement or use a larger array configuration, then build again. The exact policy is an implementation choice, but the conceptual point is important: construction depends on the hash-generated layout, and not every layout is equally easy to peel.

This is one reason an XOR filter is generally treated as a structure built from a known collection of keys. The construction is more involved than merely inserting one item into an already finalized array. If the represented set changes, the construction process may need to be repeated rather than handled like a simple in-place update.

The probability of getting stuck depends on the ratio of array size to the number of keys. A larger array relative to the key count makes it more likely that unique positions exist. Implementations typically choose an array size that is a small multiple of the key count (e.g., 1.2 to 1.5 times larger) to balance memory usage and construction success.

Querying an XOR Filter​

After construction, querying is compact and predictable.

For a query key x, the filter:

1. Computes the same three positions used during construction.
2. Reads the three fingerprint values from the array.
3. XORs those three values.
4. Computes the query key's fingerprint.
5. Compares the two results.

In pseudocode:

positions = [h1(x), h2(x), h3(x)]
observed = A[positions[0]] XOR A[positions[1]] XOR A[positions[2]]
expected = fingerprint(x)
return observed == expected

For an inserted key, construction established the equation, so the comparison succeeds. This is the no-false-negative property expected from a correctly constructed membership filter.

For a key that was not inserted, the three positions and fingerprint may nevertheless combine to the same value. If that happens, the query returns a positive result even though the key is absent. That is a false positive.

The query does not retrieve the original key, and it does not prove membership in an external authoritative sense. It only answers the probabilistic membership question encoded by the compact array.

The query's work is constant: three hash computations, three array accesses, two XOR operations, and one equality check. This predictable cost is independent of the number of keys stored, making XOR filters attractive for latency-sensitive applications.

Understanding False Positives​

False positives arise because the filter stores compressed fingerprints rather than complete keys. Many different keys can have related hash positions, and a short fingerprint has fewer possible values than a full key.

A non-member query can accidentally satisfy:

A[h1(x)] XOR A[h2(x)] XOR A[h3(x)] = f(x)

The shorter the stored fingerprint, the more opportunities there are for unrelated values to match. Increasing fingerprint size generally reduces the chance of accidental equality, but it also increases memory usage. This is a central space-versus-accuracy trade-off.

For example, if fingerprints are 8 bits, there are 256 possible values. A random non-member key has roughly a 1 in 256 chance of producing a false positive (assuming the three array values are independent and uniformly distributed, which is an approximation). If fingerprints are 16 bits, the chance drops to roughly 1 in 65,536.

The application should therefore treat a positive response as a candidate match, not as final proof. A common usage pattern is:

if filter says negative:
    skip the expensive lookup
else:
    perform the exact lookup

A negative result is useful because the filter can rule out membership. A positive result means that the item may be present and should be checked by the real data source when correctness matters.

This pattern is why XOR filters (and Bloom filters) are often used as a fast gate in front of a more authoritative but slower data structure, such as a database query or a hash table lookup.

Comparing the Idea with a Bloom Filter​

Bloom filters and XOR filters serve closely related purposes, but their internal models differ.

A Bloom filter maintains a bit array. Insertion hashes a key to multiple positions and sets those bits. Querying checks the same positions. If any required bit is clear, the key was not inserted. If all required bits are set, the result is positive, although the bits may have been set by other keys.

An XOR filter instead maintains fingerprint values in an array. Construction solves a collection of XOR equations, using peeling to find a safe assignment order. Querying reads the candidate values and XORs them together.

The contrast can be summarized as follows:

The table is intentionally qualitative. The best choice depends on the workload, implementation, fingerprint size, and required error behavior. There is no universal winner.

In practice, Bloom filters are often simpler to implement and integrate into systems that support incremental updates. XOR filters can offer better space efficiency and a more predictable query structure when the key set is known in advance.

Why an XOR Filter Can Be Attractive​

The XOR design is appealing when the key set is available for a build step and the resulting structure will be queried many times. Its query path has a fixed shape: compute three positions, read three entries, perform XOR operations, and compare a fingerprint.

The array stores more information per slot than a single Bloom-filter bit, but the representation can offer a favorable space/speed trade-off for some applications. The design also avoids the need to interpret a positive result as a collection of independently set bits; instead, it checks one combined fingerprint equation.

Specific scenarios where XOR filters shine include:

• Caching and CDN routing: A set of cached URLs or content identifiers can be built into an XOR filter. Queries are fast and space-efficient, and the filter is rebuilt periodically as the cache contents change.
• Spell checking and dictionary lookups: A dictionary of valid words can be represented compactly. Queries are quick, and false positives are acceptable because they trigger a more detailed check.
• Database bloom filters: A database index can use an XOR filter to quickly rule out non-existent records before performing a more expensive lookup.
• Network packet filtering: A router or firewall can use an XOR filter to quickly check if a packet's destination is in a known set, avoiding more expensive routing table lookups.

The main cost is construction complexity. A Bloom filter can be updated by hashing a new key and setting positions. An XOR filter requires a coordinated assignment across the entire set. The peeling algorithm, possible retries, and reverse assignment make building it a more global operation.

Complexity Intuition​

Let n be the number of keys and assume the number of hash functions is fixed at three.

The construction has several linear-looking components:

• Hashing each key takes constant work per key: O(n).
• Updating position counts takes constant work per key: O(n).
• Each key is considered during peeling: O(n).
• Each recorded key is processed once during reverse assignment: O(n).

Thus, when construction succeeds under the intended fixed-hash model, the amount of work is proportional to the number of keys. The memory used by the temporary relationships and the final array also grows with the size of the represented set.

A query performs a constant number of hash calculations, array reads, XOR operations, and one comparison. Its work does not grow with the number of keys in the set. This predictable query cost is one of the main practical attractions of membership filters.

The exact memory efficiency and false-positive behavior depend on design parameters such as the array size and fingerprint width. Those parameters should be selected according to the application's acceptable error rate and memory budget rather than treated as universal constants.

If the array size is m and the number of keys is n, the memory per key is m / n times the fingerprint width. A typical design uses m ≈ 1.2n to 1.5n, giving roughly 10–16 bits per key for an 8-bit fingerprint. This is competitive with Bloom filters, which typically use 8–12 bits per key.

Practical Design Considerations​

Treat the Filter as Probabilistic​

Do not use an XOR filter as the only source of truth when a false positive could cause an incorrect result. Use it as a fast gate in front of an exact lookup or as a way to avoid work that is known to be unnecessary.

Plan for Construction​

Because the filter is built globally, identify when and how the key set is produced. A batch build, snapshot, or periodically regenerated index is a more natural fit than a workload requiring arbitrary incremental updates. If the key set changes frequently, consider how often the filter should be rebuilt.

Use Identical Hashing During Build and Query​

The positions and fingerprints must be computed consistently. A query must use the same hash interpretation and fingerprint procedure that construction used. Any mismatch makes even inserted keys appear absent. This is a critical correctness requirement.

Select Fingerprint Width Deliberately​

Fingerprints are compact, but compactness creates the possibility of accidental matches. A larger fingerprint consumes more space while reducing false-positive risk. The correct balance depends on how expensive a positive follow-up check is and how much memory is available.

For example:

• 8-bit fingerprints: ~1 in 256 false-positive rate (rough estimate).
• 16-bit fingerprints: ~1 in 65,536 false-positive rate.
• 32-bit fingerprints: ~1 in 4 billion false-positive rate.

Choose based on your application's tolerance for false positives and the cost of a follow-up check.

Check Construction Success​

A builder should not silently assume that every hash layout peels successfully. If the process gets stuck, the implementation needs a defined response, such as rebuilding with a changed layout or configuration. The important operational requirement is that construction either produces a valid filter or reports failure clearly.

Some implementations use a retry strategy: if peeling fails, increase the array size slightly and try again. Others use multiple independent hash functions and select the one that peels most successfully.

Monitor Performance​

Track the false-positive rate in production. If it is higher than expected, it may indicate that the fingerprint width is too small or that the hash functions are not distributing keys evenly. Adjust parameters and rebuild as needed.

The Larger Algorithmic Lesson​

The most valuable idea in the XOR filter is the connection between graph structure and algebra.

At first, the problem looks like a set of overlapping equations. Each key needs three array positions whose XOR equals its fingerprint. Directly solving all equations appears difficult because every array entry may participate in multiple keys.

Peeling changes the problem. It searches for a key with a position that can be treated as its private degree of freedom. Removing that key exposes more such positions. Once an order has been found, XOR's cancellation properties make each reverse assignment straightforward.

This pattern appears broadly in algorithm design:

1. Model conflicts or dependencies explicitly.
2. Find locally removable elements.
3. Record the removal order.
4. Reverse the order to compute a globally consistent result.

Understanding this pattern is more useful than memorizing one filter implementation. It shows how a difficult global constraint system can become manageable when its dependency structure is peeled away.

Other algorithms that use similar ideas include:

• Gaussian elimination: Eliminate variables one at a time to reduce a system of linear equations.
• Topological sorting: Remove nodes with no incoming edges to find a valid ordering.
• Greedy graph coloring: Remove vertices with low degree to simplify the coloring problem.

The common theme is that a global problem can be solved by repeatedly finding and removing local simplifications.

Final Takeaways​

An XOR filter is not simply a Bloom filter with a different name. It uses a different representation and a different construction strategy.

• Three hash-derived positions connect each key to a fingerprint array.
• The construction uses peeling to find a safe order of assignments.
• The reverse phase fills array entries using XOR equations.
• A query reads three slots, XORs them, and compares the result with the query fingerprint.
• Inserted keys should produce positive results after a valid build.
• Non-inserted keys can produce false positives because fingerprints are compressed.
• The design can offer an attractive space-and-speed trade-off, but it has a more global construction process than a conventional Bloom filter.

The practical decision is therefore not whether Bloom filters have ended. It is whether the workload benefits more from the simplicity and update model of a Bloom filter or from the query behavior and representation of an XOR filter built from a known key set.

When you have a static or slowly changing set of keys, know the set in advance, and can afford a one-time construction cost, an XOR filter is worth considering. When you need to support frequent insertions and deletions, or when the key set is not known in advance, a Bloom filter or other dynamic data structure may be more appropriate.

The XOR filter is a reminder that algorithmic innovation often comes from combining simple ideas—XOR equations, graph peeling, and reverse assignment—in a novel way. Understanding these ideas helps you recognize similar patterns in other problems and design better solutions.