minisketch

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 capa

This sounds very interesting, so I tried reading some of the math in https://github.com/sipa/minisketch/blob/master/doc/math.md (I'm not great this kind of math). In my understanding, a Bloom filter, while being O(set_size), nonetheless has a small multiplier for the linear factor (in the OP I think they mentioned using 10 bits). As I read the PinSketch setup, it looks like it would actually need the full bit size of the set members, so for SHA-256 you need the full 256 bits per set member. So while PinSketch would only need O(symmetric_difference_between_sets), the element size factor is ~25 times larger? And also, in the example from the minisketch readme, it looks A still needs to send the full sketch (not just the symdiff) in the first message, right? In other words, there are a bunch of trade-offs here that might very much depend on

It's possible to be dramatically more communication efficient than bloom filters to synchronize sets. Bloom filters require O(my_set_size) bandwidth, with a good constant factor. This work optimizes it somewhat by excluding members that existed at the time of last synchronization, but it still wastes bandwidth when those commits came in from another source. It's possible to instead realize O(symmetric_difference_between_sets) when synchronizing a pair. Applied to this kind of usage the bandwidth required would be reduced by whatever redundancy factor (e.g. number of different repos you'd learn the same commit from). This can be accomplished via error correcting codes, for a high performance industrial implementation I contributed to, see: https://github.com/sipa/minisketch/ (I tried submitting this to HN a while back, but no joy--).

Network coding is very interesting but the maximum gains from the network coding itself are fairly limited... a small constant factor. In attempting to apply network coding I've found that vulnerability to (maliciously) corrupt data significantly limits the utility. If this is an area that interests you, you might also be interested in efficient set reconciliation-- where a party can communicate to another party a set using only exactly the size of the set-difference to the other parties set without having any idea of what the other parties set has. This can result in fairly large bandwidth savings in P2P gossip applications without reducing robustness-- and could be combined with network coding in places where network coding is applicable. I worked on an efficient implementation of setrecon https://github.com/sipa/minisketch/ and an ap

A collaborator and I recently had fun code golfing integer implementations of floor(106*log2(x)) and floor(log2(x!)): https://github.com/sipa/minisketch/blob/master/src/false_pos...

The minisketch library I worked on can be used for near optimal (in the sense of information leak) error correction for "set like" features: https://github.com/sipa/minisketch/ Our application is for communications efficient set reconciliation to convert Bitcoin's quadratic-overhead transaction gossip protocol (O(txn*peers)) to effectively linear (O(txn)), though the primary academic work that our work was based on were concerned with fuzzy extractors for privacy preserving (and encryption key generating) biometrics.