The power of two min-hashes for similarity search among hierarchical data objects
Sreenivas Gollapudi, Rina Panigrahy · 2008
In this study we propose sketching algorithms for comput-ing similarities between hierarchical data. Specifically, we look at data objects that are represented using leaf-labeled trees denoting a set of elements at the leaves organized in a hierarchy. Such representations are richer alternatives to a set. For example, a document can be represented as a hierarchy of sets wherein chapters, sections, and paragraphs represent different levels in the hierarchy. Such a represen-tation is richer than viewing the document simply as a set of words. We measure distance between trees using the best possible super-imposition that minimizes the number of mis-matched leaf labels. Our distance measure is equivalent to an Earth Mover’s Distance measure since the leaf-labeled trees of height one can be viewed as sets and can be recur-sively extended to trees of larger height by viewing them as set of sets. We compute sketches of arbitrary weighted trees and analyze them in the context of locality-sensitive hash-ing (LSH) where the probability of two sketches matching is high when two trees are similar and low when the two trees are far under the given distance measure. Specifically, we compute sketches of such trees by propagating min-hash computations up the tree. Furthermore, we show that prop-agating one min-hash results in poor sketch properties while propagating two min-hashes results in good sketches.