Robust Set Reconciliation via Locality Sensitive Hashing

Summary: Combine Invertible Bloom Lookup Tables with locality-sensitive hashing to perform communication-efficient robust set reconciliation in metric spaces, improving earth mover’s distance approximation from prior O(d) to O(log n). Also introduce a new per-point closeness variant with schemes that achieve sublinear communication under mild conditions. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hfd5ff4eb0bce6dbf
Venue: PODS
Year: 2019
Pagerank: 4.9793485e-05
Overall Rank: 12,137 | 18.40%
DOI: 10.1145/3294052.3319690

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Michael Mitzenmacher (Harvard University)
2. Tom Morgan (Google; Harvard University)

BibTeX Citation

@inproceedings{mitzenmacher_pods19,
        address = {New York, NY, USA},
        series = {{PODS} '19},
        title = {{Robust Set Reconciliation via Locality Sensitive Hashing}},
        url = {https://dl.acm.org/doi/10.1145/3294052.3319690},
        doi = {10.1145/3294052.3319690},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Mitzenmacher, Michael and Morgan, Tom},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
6,349	Robust Set Reconciliation	2014	SIGMOD	5.8092399e-05
12,199	Reconciling Graphs and Sets of Sets	2018	PODS	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,121	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS
2	3,236	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
3	2,969	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD
4	338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD
5	12,329	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
6	6,704	Distance-Sensitive Hashing	2018	PODS
7	12,199	Reconciling Graphs and Sets of Sets	2018	PODS
8	11,088	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS
9	13,786	Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)	2021	VLDB
10	6,349	Robust Set Reconciliation	2014	SIGMOD