Reconciling Graphs and Sets of Sets

Summary: Generalizes set reconciliation to sets of sets, parameterized by child-set size, universe, and minimum-matching difference d. Develops protocols for reconciling G(n,p) graphs and rooted forests, with applications to databases and document collections. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 1767
Venue: PODS
Year: 2018
Pagerank: 5.093636e-05
Overall Rank: 11,899 | 18.37%
DOI: 10.1145/3196959.3196988

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 (Harvard University)

BibTeX Citation

@inproceedings{mitzenmacher_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Reconciling Graphs and Sets of Sets}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196988},
        doi = {10.1145/3196959.3196988},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Mitzenmacher, Michael and Morgan, Tom},
        year = {2018}
}

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 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
3,358	An efficient reconciliation algorithm for social networks	2014	VLDB	7.4900538e-05
7,520	Growing a Graph Matching from a Handful of Seeds	2015	VLDB	5.6029996e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS
2	2,782	Interaction between Record Matching and Data Repairing	2011	SIGMOD
3	7,520	Growing a Graph Matching from a Handful of Seeds	2015	VLDB
4	3,251	Keys for Graphs	2015	VLDB
5	3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD
6	3,358	An efficient reconciliation algorithm for social networks	2014	VLDB
7	3,474	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB
8	13,472	Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)	2021	VLDB
9	11,836	Robust Set Reconciliation via Locality Sensitive Hashing	2019	PODS
10	6,220	Robust Set Reconciliation	2014	SIGMOD