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 t

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.