Optimal method saves time and data in set difference tasks
Toward Optimal Time-Space Tradeoffs for Set Reconciliation
Data Structures and Algorithms
Summary
When two computers try to find out what items they have differently from a huge list, it usually takes a lot of time or a lot of data exchanged. The authors propose a new method called XYZ-Sketch that uses almost the smallest amount of data possible while updating information very quickly. Their method works well when the difference between the sets is large enough and decodes the differences efficiently. They also provide a mathematical model showing their method is close to the best possible. Experiments confirm the method performs as expected.
What this means in practice
- •For distributed systems engineers: Optimize data synchronization between servers by reducing communication while keeping update time very low in finding data differences.
- •For database administrators: Speed up incremental data reconciliation tasks with minimal network bandwidth for large datasets whose differences must be identified.
Authors
Rui Xu, Kangyang Zhou, Jiachen Xu, Jiarui Guo, Boyu Xian, Kaicheng Yang, Tong Yang, Yong Cui
Abstract
Set reconciliation, where two parties each holding a large set of elements aim to identify their set difference, is a fundamental task in many areas. There are two important metrics in this problem: time (computation cost) and space (communication cost). Most previous work focuses on optimizing one metric at the expense of the other. We present XYZ-Sketch, proving that it is possible to achieve near-minimal space and $O(1)$ time updates simultaneously. Specifically, for sufficiently large $d$, XYZ-Sketch reconciles sets with only $(1+\varepsilon)d$ elements for communication, while achieving $O(1)$ insertion time and $O(d\log V)$ decoding time. Here, $d$ and $V$ denote the size of the difference between two sets and the universe size, respectively. We further establish a broad fixed-support canonical model for the problem, showing that, under an open extremality conjecture, XYZ-Sketch is asymptotically optimal within this model. Experiments validate the predicted near-optimal performance of XYZ-Sketch. The source code is available at https://github.com/djwj233/XYZ-Sketch.