arXiv preprint ·
Toward Optimal Time-Space Tradeoffs for Set Reconciliation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity
A Strongly Subquadratic $(3+\varepsilon)$-Approximation for Weighted Edit Distance over Arbitrary Metrics
Sharp Norms from Finite Structure: Graph Matrices and Structured Chaoses
Fast Stencil Computations on a Single Arbitrarily Moving Interval
Approximating Optimal Welfare in Complementary Allocation under Decentralized Information
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.