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: 1752
Venue: PODS
Year: 2019
Pagerank: 4.1945683e-05
Overall Rank: 11,642 | 19.01%
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
2. Tom Morgan

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4,297	Robust Set Reconciliation	2014	SIGMOD	6.2885419e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,357	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS	4.1945683e-05
8,763	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.456315e-05
5,902	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.2796864e-05
3,938	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB	6.6155909e-05
4,243	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	6.32976e-05
605	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.000193396
11,833	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1945683e-05
10,351	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	4.1945683e-05
13,270	Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)	2021	VLDB	-
4,297	Robust Set Reconciliation	2014	SIGMOD	6.2885419e-05