Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Extending That XOR Trick to Billions of Rows

nochlin.com

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Extending That XOR Trick to Billions of Rows

#11

Post by nullc »

iblt has low space efficiency for small sets, small elements, and low failure rates (and on that note is only probabilistic in its success).

We implemented https://github.com/bitcoin-core/minisketch which has optimal size efficiency-- N bits of state will always correctly recover when there are N or fewer bits of set difference, even when the set elements are small (like 32 bits, for example).

So for example you can you and I can each have sets of, say, ten thousand 32-bit elements which are identical except for 10 entries, and I can send you a 320 bit (32*10) sketch of my set and from that you can always determine the 10 (or fewer) differences. The same element and difference size with IBLT would likely take thousands of bits to have a low failure rate.

The downside is that the minisketch approach has quadratic decode complexity in the size of the set difference, but this is not a big deal when the number of differences is small by construction or thanks to recursive subdivision.

For cases where the differences are large iBLT eventually wins out-- the two ideas can also be hybridized in a variety of ways. E.g. using minisketch to make multi-element buckets in an iblt analogous to blocked bloom filter or the normal practice with cuckoo filters.

Another related scheme is cpisync which was used for many years by SKS key servers. It has communications efficiency like minisketch, but cubic decode costs.

Re: Extending That XOR Trick to Billions of Rows

#12

Post by fc417fc802 »

nromiun wrote: post #7
JPLeRouzic wrote: post #6

Earlier quoted context omitted.

I know XOR only in the context of binary numbers. Is this "XOR trick" more general?

Every number on computers is converted to binary internally, so yes this works on decimal numbers too.

> 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.

Re: Extending That XOR Trick to Billions of Rows

#13

Post by hyperhello »

fc417fc802 wrote: post #12
nromiun wrote: post #7

Earlier quoted context omitted.

Every number on computers is converted to binary internally, so yes this works on decimal numbers too.

> 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.

Re: Extending That XOR Trick to Billions of Rows

#14

Post by nyrikki »

dataflow wrote: 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.

> Finally, they introduce Invertible Bloom Filters, which add an exact get operation and a probabilistic listing operation.

I haven't spent time digging into the implementation details, but the exact get should allow for verification.

It is not uncommon to use probabilistic methods to reduce search space.

Re: Extending That XOR Trick to Billions of Rows

#15

Post by dataflow »

nyrikki wrote: post #14
dataflow wrote: 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.

> Finally, they introduce Invertible Bloom Filters, which add an exact get operation and a probabilistic listing operation. I haven't spent time digging into the implementation details, but the exact get should allow for verification. It is not uncommon to use probabilistic methods to reduce search space.

I haven't dug into the gory details either, but later they say:

> To fully generalize this into a robust data structure, we need:

> (1) A partitioning scheme that creates recoverable partitions with high probability

> (2) An iterative process that uses recovered values to unlock additional partitions

And they also say:

> With proper sizing (typically m > 1.22d cells), IBFs recover the full symmetric difference with very high probability.

It really doesn't sound like this is both exact and also running in linear time like XOR... right? Perhaps somehow the error is one-sided but then the time bound is probabilistic? If I'm missing something and they're truly maintaining both an absolute guarantee and an absolute time bound, this is mindblowing! But I don't get that impression?

Re: Extending That XOR Trick to Billions of Rows

#16

Post by javcasas »

So the XOR initial trick is: use a hash to partition the data into batches so that each batch has up to 1 missing element.

Can't we use this again? I mean:

1. Partition the data so that some batches have up to 1 missing element.

2. Recover the elements where possible with the XOR trick.

3. Pick another hash function, then repeat finding more missing elements.

4. Repeat until no more missing elements.

Re: Extending That XOR Trick to Billions of Rows

#17

Post by hundredwatt »

dataflow wrote: 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.

Re: Extending That XOR Trick to Billions of Rows

#18

Post by dzaima »

javcasas wrote: post #16

So the XOR initial trick is: use a hash to partition the data into batches so that each batch has up to 1 missing element. Can't we use this again? I mean: 1. Partition the data so that some batches have up to 1 missing element. 2. Recover the elements where possible with the XOR trick. 3. Pick another hash function, then repeat finding more missing elements. 4. Repeat until no more missing elements.

A property of the initial XOR trick for 2 different elements is that it guarantees finding a way to partition in one pass (and with very trivial code; no hashing involved!), which is lost by replacing that with hashing. (the original trick does take two passes - finding the bit to partition on, and doing the actual partitioning, whereas hashing is 1+ε passes, but the first pass in the original is just an xor-fold, and the partitioning really only needs to be a "accumulator ^= (current_val & mask) ? current_val : 0" (other partition is just xoring the results of both passes), both of which can be trivially parallelized and SIMD'd with O(1) extra memory usage)

The approach in my comment achieves guaranteeing finding partitions, and still avoids actual hashing or anything strictly-probabilistic, but does still lose the extreme triviality and mechanical sympathy of the original approach.

Re: Extending That XOR Trick to Billions of Rows

#19

Post by hundredwatt »

javcasas wrote: post #16

So the XOR initial trick is: use a hash to partition the data into batches so that each batch has up to 1 missing element. Can't we use this again? I mean: 1. Partition the data so that some batches have up to 1 missing element. 2. Recover the elements where possible with the XOR trick. 3. Pick another hash function, then repeat finding more missing elements. 4. Repeat until no more missing elements.

The graph constructed by using bloom filter-style hash functions supports a decoding process called "peeling" where you:

1. Find a batch with 1 missing element 2. Delete that element from its other assigned partitions 3. Repeat, as the modified batches may now be recoverable

This iterative process (surprisingly!) succeeds with very high probability as long as the number of partitions is 1.22x larger than the number of missing elements with k=3 hash functions.

Re: Extending That XOR Trick to Billions of Rows

#20

Post by nullc »

dataflow wrote: post #15
nyrikki wrote: post #14

Earlier quoted context omitted.

> Finally, they introduce Invertible Bloom Filters, which add an exact get operation and a probabilistic listing operation. I haven't spent time digging into the implementation details, but the exact get should allow for verification. It is not uncommon to use probabilistic methods to reduce search space.

I haven't dug into the gory details either, but later they say: > To fully generalize this into a robust data structure, we need: > (1) A partitioning scheme that creates recoverable partitions with high probability > (2) An iterative process that uses recovered values to unlock additional partitions And they also say: > With proper sizing (typically m > 1.22d cells), IBFs recover the full symmetric difference with v…

There is no absolute guarantee. You can have an arbitrarily large multiple and the decode can still fail when a set of entries exist that form a cycle, it just becomes quite unlikely as the overhead goes up.

One of the ways of hybridizing iblt and exact algebraic techniques like the minisketch library I link in my other post is to staple a small algebraic sketch to the iblt. If the iblt is successful you're done, if it gets stuck you use take the recovered elements out of the algebraic sketch and decode that. It's fast to decode the algebraic sketch in spite its O(n^2) behavior because it's small, and it'll always be successful if there are few enough elements (unlike the iblt).

Sadly this still doesn't give a guarantee since you might have more elements in a cycle than the size of the backup, but small cycles are more likely than big ones so there exists a range of sizes where it's more communications efficient than a larger iblt.

Post reply on HN