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)
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 |
|---|
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 20 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00057568153 |
| 1,531 | Change Detection in Hierarchically Structured Information | 1996 | SIGMOD | 0.0001033805 |
| 4,663 | Approximate Matching of Hierarchical Data Using pq-Grams | 2005 | VLDB | 6.4810192e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 927 | SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search | 2014 | VLDB |
| 2 | 5,527 | DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search | 2024 | VLDB |
| 3 | 5,987 | SetSketch: Filling the Gap between MinHash and HyperLogLog | 2021 | VLDB |
| 4 | 2,505 | DSH: Data Sensitive Hashing for High-Dimensional k-NN Search | 2014 | SIGMOD |
| 5 | 9,674 | MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances | 2023 | VLDB |
| 6 | 6,137 | Scaling Similarity Joins over Tree-Structured Data | 2015 | VLDB |
| 7 | 5,796 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS |
| 8 | 6,704 | Distance-Sensitive Hashing | 2018 | PODS |
| 9 | 3,108 | Similarity Evaluation on Tree-structured Data | 2005 | SIGMOD |
| 10 | 20 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB |