3 ms·

Thanks 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

Thanks 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 ago
Yeah, 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.