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: 1461
Venue: PODS
Year: 2008
Pagerank: 4.1945683e-05
Overall Rank: 12,357 | 14.04%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Sreenivas Gollapudi
2. Rina Panigrahy

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
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
1,390	Change Detection in Hierarchically Structured Information	1996	SIGMOD	0.00012248349
4,406	Approximate Matching of Hierarchical Data Using pq-Grams	2005	VLDB	6.2141638e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
682	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00018201541
1,229	SK-LSH : An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB	0.00013157271
6,376	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB	5.0916875e-05
5,200	SetSketch: Filling the Gap between MinHash and HyperLogLog	2021	VLDB	5.6337581e-05
3,056	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD	7.6432146e-05
9,303	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB	4.358026e-05
6,241	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1411469e-05
8,763	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	4.456315e-05
3,199	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.3927291e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636