The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects

Summary: Sketching/LSH for leaf-labeled hierarchical objects (weighted trees) using min-hash propagation to capture an EMD-like minimum-superimposition distance (set-of-sets view). Prove one propagated min-hash gives poor guarantees while two min-hashes suffice to obtain strong collision-separation properties for similarity search. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1460
Venue: PODS
Year: 2008
Pagerank: 5.093636e-05
Overall Rank: 12,550 | 13.90%
DOI: 10.1145/1376916.1376946

Incoming Non-self Citations Over Time

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

Authors

1. Sreenivas Gollapudi (Microsoft)
2. Rina Panigrahy (Microsoft)

BibTeX Citation

@inproceedings{gollapudi_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376946},
        doi = {10.1145/1376916.1376946},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Gollapudi, Sreenivas and Panigrahy, Rina},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
1,496	Change Detection in Hierarchically Structured Information	1996	SIGMOD	0.00010569165
4,566	Approximate Matching of Hierarchical Data Using pq-Grams	2005	VLDB	6.6275286e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	990	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB
2	5,800	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
3	5,864	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB
4	2,673	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD
5	9,493	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB
6	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
7	5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
8	6,583	Distance-Sensitive Hashing	2018	PODS
9	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
10	21	Similarity Search in High Dimensions via Hashing	1999	VLDB