In the previous articles in the series, we saw several implementations of filters with a common set of operations, including additions and (not always) removals. Here we'll study XOR Filters, which after creation do not permit any change to its values, but provide great performance with low memory requirements.
XOR Filters
An XOR Filter (XF) is another probabilistic search data structure, invented rather recently by Thomas Mueller Graf and Daniel Lemire in their 2020 article "XOR Filters: Faster and Smaller Than Bloom and Cuckoo Filters". Like the previous filters we saw, if asked whether some value is stored in it, it will reply either "absent" with 100% certitude (no false negatives), or "may be present" (with a certain probability of a false positive). Compared to the previous filters, an XF is smaller and faster to query, but at a cost: you build it once from the full data set, and you cannot add or remove values afterward unless you rebuild it from scratch.
(Another difference we had already mentioned in a previous article is that the create operation will take the whole array of items to be stored instead of just the expected number, and there will be no add or remove operations, just find to search the filter.)
How does an XF work? The core idea is to use an array (call it B) divided into three blocks of p-bit slots; the original article allowed different block sizes, but for simplicity we'll make them equal length. For each x value, we have:
- three hash positions (h₀(x), h₁(x), and h₂(x)), one for each block
- a p-bit fingerprint fp(x)
The array is built in a special way (which we'll soon see) so for every key in the set, it holds that fp(x) = B[h₀(x)] XOR B[h₁(x)] XOR B[h₂(x)]_. So, how do we query it? To check whether a value is in the XF, compute its fingerprint and hashes, then check whether the equality holds; if not, the value definitely isn't in the XF.
Sizing an XOR Filter
Let's start with the fingerprint size. If x was never inserted in the XF, the three cells hold values determined by other keys, and the XOR will in effect produce a random p-bit number, which will match fp(x) with false-positive probability ε=2^(‑p), so p=8 gives ε≈ 0.39%, p=16 gives ε ≈ 0.0015%, and p=24 goes down to 0.00000596%.
Now, for the array size. For n values, the array size is about 1.23_n_; for smaller n, adding 32 is recommended. The 1.23 constant comes from a threshold for a "peeling" graph algorithm we'll use; that number makes it very probable that the procedure succeeds.
The following code is part of the XF creation function; we'll get to the rest later.
const EPSILON = 0.01;
const createXorFilter = (items, eps = EPSILON) => {
➊const p = Math.ceil(Math.log2(1 / eps));
if (p > 24) {
throw new Error(
"XOR filter: epsilon exceeds 24-bit fingerprint limit"
);
}
➋const s = Math.ceil((1.23 * items.length) / 3);
if (items.length === 0) {
return { p, seed: 0, s: 0, b: [] };
}
// array generation code, clipped out
};
According to the formula for ε ➊ we can calculate the number of bits by taking logarithms; we use the ceiling function for safety; longer fingerprints reduce the false positive probability. For simplicity, we want the length of the array to be a multiple of 3 ➋ so we calculate the block size using the ceiling function.
The returned object has:
-
pis the fingerprint length -
seedis used for the three hashing functions -
sis the length of each block -
bis the generated array; its length is3*s
We'll see the rest of the code soon (which includes how to calculate the contents of the b array) but let's look at the fingerprint and hashes now.
➊const fingerprintOf = (value, bits) =>
hashWithSeed(value, 0) & ((1 << bits) - 1);
➋const h0 = (value, seed, s) =>
hashWithSeed(value, 3 * seed + 1) % s;
const h1 = (value, seed, s) =>
s + (hashWithSeed(value, 3 * seed + 2) % s);
const h2 = (value, seed, s) =>
2 * s + (hashWithSeed(value, 3 * seed + 3) % s);
➌const indicesOf = (value, seed, s) => [
h0(value, seed, s),
h1(value, seed, s),
h2(value, seed, s)
];
To find the fingerprint ➊ we use the same hashWithSeed function we've been using, masking it to keep just a given number of bits; when using the function, we'll pass the p value we calculated. Next ➋ we have the three hash functions; we pass the block size s and we use three different seeds, so the hashes are independent. Finally ➌ the indicesOf function just returns an array with the three calculated hashes; we'll use it for searching.
We're still missing the rest of the XF creation code, but we can look at how to search it with some examples. See Figure 11½–24.
Figure 11½–24: Searching an XOR Filter for the 6 added values
We created the XF with the 6 values on the left: GROUCHO, HARPO, CHICO, ZEPPO, GUMMO, and BROTHERS. At the top of the image, we have the array with 9 values, divided into three blocks. The values for the slots were calculated by the algorithm we'll introduce in the next section. For each value, we have its hexadecimal 8-bit fingerprint (fp) and the three calculated hashes.
How do we search? Take GROUCHO, for example:
- Calculate its fingerprint (
3A) - Calculate its three hashes, one into each block
- Calculate the XOR of the three corresponding slot values,
7C,C5, and83; the result is3A - Since the fingerprint and the XOR result match, the search is successful
Let's look at two searches for values not in the original set: ABBOTT, which is reported as not being in the set, and COSTELLO, which produces a false positive. See Figure 11½–25.
Figure 11½–25: A failed search and a false positive
What happens in these cases?
For
ABBOTT, its fingerprint is42, its slot values are89,A6, and83and the XOR of these three values isAC, which doesn't match42- we get a 100% negativeFor
COSTELLO, the fingerprint is46, which happens to match the XOR of the three slots, so we get a false positive.
The search code is as follows.
const find = (filter, value) => {
➊if (filter.s === 0) return false;
➋const [i1, i2, i3] = indicesOf(value, filter.seed, filter.s);
➌return (
fingerprintOf(value, filter.p) ===
(filter.b[i1] ^ filter.b[i2] ^ filter.b[i3])
);
};
First, we check ➊ whether the XF is empty; it doesn't make sense to return a false positive when we know it's empty. Then, we find the three positions to check ➋ and finally we compare the calculated fingerprint with the XOR of the three positions ➌.
Now let's finish by completing the XF creation code.
Creating an XOR Filter
The key detail is how to calculate the B values so the XOR results match the expected fingerprints. Let's start by looking at which slots are involved for each value; see Figure 11½–26.
Figure 11½–26: The "peeling" algorithm decides which slot belongs to which entry
We have to assign values to the slots so the XOR works. Let's see:
-
BROTHERSis the only value that needs slot #5; given the values for slots #2 and #8, we can calculate the value for slot #5 so the XOR produces the correct fingerprint. We can "peel"BROTHERSoff, and after determining the rest of the slots, we can come back to it and finish the job by calculating slot #5. We will say thatBROTHERSowns slot #5 and uses slots #2 and #8. Also, let's forget theBROTHERSrow of the table for now; imagine it gone. -
GROUCHOis a similar case; it's the only value that needs slot #7, so it will own it (and use slots #0 and #3); we'll "peel" it off for later (when we'll be able to set slot #7 so the XOR calculation works out) and ignore that row for now. -
ZEPPOis interesting; it needs slots #2, #4, and #6, but having "forgotten" the rows forBROTHERSandGROUCHO, we can peelZEPPOoff and let it own slot #2. When the time comes, we'll be able to calculate slot #2 so the XOR produces the correct fingerprint. - To sum up the rest,
CHICOcan be peeled off next, owning slot #0; thenHARPOowning slot #3; and finallyGUMMOowning slot #4.
What comes next? Initially, all slots are set to 00. Let's walk backward through the set of peeled values.
- We can let slots #1 and #8 be
00and set slot #4 to17to match the fingerprint toGUMMO. Three slots are now final. - For
HARPOwe already have slot #1 set to00; we can let slot #6 at00and set the owned slot #3 to matchC5. We now have five final slot values. - Working with
CHICOwe can set the owned #0 slot so its XOR with slots #4 (17) and #6 (00) produces6B; the slot is set to7C, and we have six final slot values. - The process is similar for
ZEPPO(setting slot #2, taking into account the already set #4 and #6 slots), thenGROUCHO(setting its owned slot #7 considering the values for slots #0 and #3), and finallyBROTHERS(setting its owned slot #5, the last one).
How is this implemented? Let's analyze the rest of the code for createXorFilter.
const createXorFilter = (items, eps = EPSILON) => {
// calculation of p and s, shown earlier, snipped out
➊const MAX_SEEDS = 1000;
for (let seed = 0; seed < MAX_SEEDS; seed++) {
➋ const indices = items.map((item) =>
indicesOf(item, seed, s)
);
➌ const itemCounts = new Uint32Array(3 * s);
const xors = new Uint32Array(3 * s);
➍ indices.forEach((itemIndices, itemIndex) => {
itemIndices.forEach((index) => {
itemCounts[index]++;
xors[index] ^= itemIndex;
});
});
➎ const queue = [];
itemCounts.forEach((count, index) => {
if (count === 1) {
queue.push(index);
}
});
➏ const peeled = [];
for (let head = 0; head < queue.length; head++) {
const index = queue[head];
➐ if (itemCounts[index] === 1) {
const itemIndex = xors[index];
peeled.push([itemIndex, index]);
for (const other of indices[itemIndex]) {
itemCounts[other]--;
xors[other] ^= itemIndex;
if (itemCounts[other] === 1) {
queue.push(other);
}
}
}
}
➑ if (peeled.length === items.length) {
const b = new Uint32Array(3 * s);
const mask = (1 << p) - 1;
➒ for (let j = peeled.length - 1; j >= 0; j--) {
const [itemIndex, index] = peeled[j];
let fp = fingerprintOf(items[itemIndex], p);
indices[itemIndex].forEach((i) => {
fp ^= b[i];
});
➓ b[index] = (fp ^ b[index]) & mask;
}
return { p, seed, s, b };
}
}
throw new Error(
"XOR filter: could not construct a peelable filter"
);
};
There's one issue ➊ we haven't discussed yet. As we described the "peeling" algorithm, it works as long as you can find columns used by only one remaining yet-unpeeled item… but is this guaranteed? The fact is, if you have bad luck, two different items could hash to the same three slots, and that would stop the algorithm cold. There's a simple solution that will almost certainly work: use a seed to calculate the three hashes, and if the algorithm fails, switch to another seed and try again. Obviously, we cannot keep attempting this, so some limit has to be set; if after MAX_SEEDS different seeds we keep failing, we'll give up.
What do we do in each attempt? The indices array ➋ will just store the three hashes for each item. The itemCounts array ➌ will count how many items use that slot, and the xors array stores the XOR of all the item indices that use the slot; as items get peeled away, their indices are XORed out, so when the count reaches 1, xors will have the index of the item that will own the slot.
We will push indices of the slots with just one user into the queue array ➎ and we'll start the "peeling" algorithm. We'll track the peeled items in the peeled array ➏ and start assigning values. The test at ➐ matters: we queue elements that use a single slot, but when we "remove" its row, we decrement counts in three buckets, so another bucket's count may drop from 1 to 0. When decrementing slot counts, if some other slot ends up associated with just one item, we push it into the queue for future processing.
Final processing ➑ starts by testing whether every item was peeled (and, if not, we loop again with another seed) and computes masks. We go down the peeled list in reverse order ➒ and do calculations so the XOR of the three slots matches the item's fingerprint; the key line is the assignment to b[index] ➓.
Bye for now! In the next article in the series, we will look at Ribbon Filters, which work similarly to XOR Filters but with even less memory overhead.
Top comments (0)