4 ms·
That does sound like absolute magic. One hundred million? I didn't know about this algorithm, and it looks revolutionary for a ton of things. If sketch size gr
by api 6y ago
That does sound like absolute magic. One hundred million? I didn't know about this algorithm, and it looks revolutionary for a ton of things.
If sketch size grows with only log(n) where N is the set size, then we are talking about practical efficient non-thrashing replication of billions of records at broadband speeds.
(insert mind=blown meme...)
- pwuille 6y agoI think the most mind-blowing aspect about it is that (PinSketch) sketches are identical in size to the bandwidth that would be required to just send the difference if you did know it ahead of time. Perhaps this intuition helps: imagine we have sets of positive numbers, and we know that the difference is at most 1 element. So there is one element that you have but I don't, or the other way around. In this case there is a very easy solution: just send the sum of all your elements. If it's larger than the sum of the receiver's element, the (absolute value of the) difference is exactly the element that one party has and the other doesn't. In a way, PinSketch is generalizing this "send sum of your elements" in such a way that it works for more than one difference.