On Feb 25, 2010, at 7:22 AM, Yaron Minsky wrote: > > The use of the prefix tree is described in the two articles Set > Reconciliation with Nearly Optimal Communication Complexity and > Practical Set Reconciliation. You will find them on the Google code > page¹. The mathematics are quite involved though. It is the > information that is needed for two servers to know what keys they need > to exchange. > > Indeed. The data structure is called a prefix-tree in the paper (hence > PTree). Basically, it's a binary tree that holds a special kind of checksum > for different subsets of the keyspace, dividing the space of keys up as you > go down the tree. >
The partition tree in section 4 of "Practical Set Reconciliation"? That looks like what you are describing. Thanks! 73 de Jeff
_______________________________________________ Sks-devel mailing list Sks-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/sks-devel
