Live data from Hacker News

Extending That XOR Trick to Billions of Rows

nochlin.com

21–25 of 25 posts

Re: Extending That XOR Trick to Billions of Rows

#21
post #2

Before you get too excited, this is a probabilistic algorithm, not a deterministic one. Feels weird to call it an "extension" when you lose an absolute guarantee, but still cool nonetheless.

You don't lose absolute guarantees, but the probabilistic nature means the process may fail (in a guaranteed detectable way) in which case you can try again with a larger parameter. The "bloom filter" name is misleading in regard to this.

> (in a guaranteed detectable way)

To be pedantic, not guaranteed. The xor of multiple elements may erroneously have a passing checksum, resulting in an undetected false decode. You can make the probability of this as low as you like by using a larger checksum, but the initial HN example was IIRC a list of 32-bit integers, so using a (say) 128 bit checksum to make false decodes 'cryptographically unlikely' would come at a rather high cost since it's a size added to each bucket.

If your sent members are multi-kilobyte contact database entries or something than the overhead required to make false decode impossible would be insignificant.

This limitation also applies somewhat to the alternative algebraic approach in my comments-- an overfull sketch could be falsely decoded--, except the added size needed to make a false decode cryptographically unlikely is very small and goes down relative to the size of the sketch as the sketch grows instead of being linear in the size of the sketch.

I haven't looked at your implementation but it can be useful to have at least 1 bit counter or just make the LSB of your checksum always 1. Doing so prevents falsely decoding an overfull bucket with an even number of members in it, and since the distribution of members to bucket is binomial 2 is an extremely common number for overfull buckets. You can use a counter bigger than 1 bit (and combine it with addition in its ring rather than xor), but the tradeoff vs just having more checksum bits is less obvious.

It's probably an interesting open question about the existence of checksums such that the xor of 2..N valid codewords is unlikely to be a valid codeword... the "always emit 1" function has perfect performance for even values but are there schemes that still contribute distance even in cases were the N isn't completely precluded?

Re: Extending That XOR Trick to Billions of Rows

#22
post #21

Earlier quoted context omitted.

You don't lose absolute guarantees, but the probabilistic nature means the process may fail (in a guaranteed detectable way) in which case you can try again with a larger parameter. The "bloom filter" name is misleading in regard to this.

> (in a guaranteed detectable way) To be pedantic, not guaranteed. The xor of multiple elements may erroneously have a passing checksum, resulting in an undetected false decode. You can make the probability of this as low as you like by using a larger checksum, but the initial HN example was IIRC a list of 32-bit integers, so using a (say) 128 bit checksum to make false decodes 'cryptographically unlikely' would come…

> To be pedantic, not guaranteed. The xor of multiple elements may erroneously have a passing checksum, resulting in an undetected false decode

The false decodes can be detected. During peeling, deleting a false decode inserts a new element with the opposite sign of count. Later, you decode this second false element and end up with the same element in both the A / B and B / A result sets (as long as decode completes without encountering a cycle).

So, after decode, check for any elements present in both A / B and B / A result sets and remove them.

--

Beyond that, you can also use the cell position for additional checksum bits in the decode process without increasing the data structure's bit size. i.e., if we attempt to decode the element X from a cell at position m, then one of the h_i(x) hash functions for computing indices should return m.

There's even a paper about a variant of IBFs that has no checksum field at all: https://arxiv.org/abs/2211.03683. It uses the cell position among other techniques.

Re: Extending That XOR Trick to Billions of Rows

#23
post #21

Earlier quoted context omitted.

> (in a guaranteed detectable way) To be pedantic, not guaranteed. The xor of multiple elements may erroneously have a passing checksum, resulting in an undetected false decode. You can make the probability of this as low as you like by using a larger checksum, but the initial HN example was IIRC a list of 32-bit integers, so using a (say) 128 bit checksum to make false decodes 'cryptographically unlikely' would come…

> To be pedantic, not guaranteed. The xor of multiple elements may erroneously have a passing checksum, resulting in an undetected false decode The false decodes can be detected. During peeling, deleting a false decode inserts a new element with the opposite sign of count. Later, you decode this second false element and end up with the same element in both the A / B and B / A result sets (as long as decode completes…

[deleted]

Re: Extending That XOR Trick to Billions of Rows

#24

Earlier quoted context omitted.

> so yes this works on decimal numbers too. Given that rounding tends to be necessary that seems extremely questionable in practice. Similar to how the equality operator in most (probably all) languages can be used with floating point numbers but in most cases that is a very bad idea.

Integers don’t have to be stored as floating point.

And yet a great many applications that use numbers with a decimal point will involve rounding and/or inexact matches.

Re: Extending That XOR Trick to Billions of Rows

#25
post #5

It would be nice if they explained what XOR trick that is. It seems to have something to do with finding missing numbers in a list?

It's a solution to the problem: given a list of n-1 unique integers 1 through n, find the missing integer. The trick is that when you xor all of the numbers in the list together and then xor that with the xor of 1 through n, the result is the missing number.

>the xor of 1 through n

XOR[0...x] = (x&1^(x&2)>>1)+x*(~x&1)

Of course, you don't have to do this with xor, you can do it with just addition (mod wordmax) and the well known identity attributed to gauss will support you.

Post reply on HN