Robust Set Reconciliation

Summary: Robust set reconciliation via earth mover's distance to tolerate near-duplicate elements, not exact matches. Presents a communication- and time-efficient algorithm with provable guarantees and a matching lower bound, plus strong empirical results. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4961
Venue: SIGMOD
Year: 2014
Pagerank: 5.9425753e-05
Overall Rank: 6,220 | 57.33%
DOI: 10.1145/2588555.2610528

Incoming Non-self Citations Over Time

Authors

1. Di Chen (Hong Kong University of Science and Technology)
2. Christian Konrad (Reykjavik University)
3. Ke Yi (Hong Kong University of Science and Technology)
4. Wei Yu (Aarhus University)
5. Qin Zhang (Indiana University)

BibTeX Citation

@inproceedings{chen_sigmod14,
        title = {{Robust Set Reconciliation}},
        author = {Chen, Di and Konrad, Christian and Yi, Ke and Yu, Wei and Zhang, Qin},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2610528},
        url = {https://dl.acm.org/doi/10.1145/2588555.2610528},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,836	Robust Set Reconciliation via Locality Sensitive Hashing	2019	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,423	Consistency Rationing in the Cloud: Pay only when it matters	2009	VLDB	0.00010822279
2,228	Data Consistency Properties and the Trade-offs in Commercial Cloud Storages: the Consumers’ Perspective	2011	CIDR	8.9082751e-05
2,770	Relaxed Currency and Consistency: How to Say "Good Enough" in SQL	2004	SIGMOD	8.1458395e-05
6,827	Sampling Dirty Data for Matching Attributes	2010	SIGMOD	5.7616041e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,472	Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)	2021	VLDB
2	6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD
3	2,299	A Locking Protocol For Resource Coordination In Distributed Databases	1978	SIGMOD
4	13,098	A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols	1991	PODS
5	1,733	Reconciling while Tolerating Disagreement in Collaborative Data Sharing	2006	SIGMOD
6	13,174	Transaction Commitment At Minimal Communication Cost	1987	PODS
7	10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS
8	12,671	Randomized Algorithms for Data Reconciliation in Wide Area Aggregate Query Processing	2007	VLDB
9	11,899	Reconciling Graphs and Sets of Sets	2018	PODS
10	11,836	Robust Set Reconciliation via Locality Sensitive Hashing	2019	PODS