4 ms·
Hi, other author here. 0. Indeed. Though if your set consists of 100 million elements, you'll indirectly need to have at least 27 bit elements just to be able
by pwuille 6y ago
Hi, other author here.
0. Indeed. Though if your set consists of 100 million elements, you'll indirectly need to have at least 27 bit elements just to be able to identify them. So for practical problems you can probably say that the sketch size does grow logarithmitically with the set sizes.
1. The capacity scales with the symmetric difference between the sets. So if one party has [A,B,C] and the other has [B,C,D,E], you need capacity 3 (for A,D,E). So every "change" to an element costs at most 2 capacity; insertions/deletions each cost 1 capacity.
2. Sketch size is exactly (element size in bits)*capacity. So 1000 bits for a sketch with capacity of 100 10-bit elements.
3. I'm not really up to date here. I believe that PinSketch is the best known deterministic reconciliation (meaning that reconstruction is guaranteed to succeed if the capacity is sufficient). There are more performant algorithms and more trade-offs to make (between capacity and probility, e.g.) if you allow probabilistic recovery.
4. I just wrote a (slow) native Python re-implementation for demonstration/testing purpose: https://github.com/sipa/minisketch/pull/26 https://github.com/sipa/minisketch/pull/26. The C++ code relies on many low-level optimizations that are hard to replicate in higher level languages, so expect a very serious performance drop.
1. Shouldn't be hard to compile to WASM with emscripten, but I haven't tried.
- ignoramous 6y agoThanks a lot. I have use for something exactly like minisketch but need to interface it with JavaScript. I'll take a stab at it with Emscripten. Can you point towards other performant algorithms? IBLT, from the minisketch GitHub readme at least, seems wasteful in terms of space. If you're aware: What'd be a comparable data structure to Pin Sketches for membership checks (whether "X" exists in a set of, say, 100M records). Minimal Acyclic Finite State Automata (MA-FSA) and Succinct Tries come to mind but those aren't optimal though deterministic.
- pwuille 6y agoYeah, IBLT has a size overhead which mostly matters for small differences/capacities. It's also probabilistic, so the higher your probability for recovery has to be, the larger it gets. Assuming you don't actually know an strict upper bound on the symmetric difference size before reconciliation, PinSketch of course also becomes probabilistic. On the other hand, IBLT is very fast (and linear in the capacity; PinSketch is quadratic in the capacity). A data structure for set lookups? Sounds like a Bloom filter. If you want it deterministic, just send the set in sorter order say? I don't think there is much fancy possible here.
- api 6y agoThat 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.