The power of two min-hashes for similarity search among hierarchical data objects

ABSTRACT

In this study we propose sketching algorithms for computing 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 representation 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 mismatched 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 recursively 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 hashing (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 propagating one min-hash results in poor sketch properties while propagating two min-hashes results in good sketches.

REFERENCES

• 1: N. Augsten, M. Böhlen, C. Dyreson, and J. Gamper. Approximate joins for data-centric XML. In Proceedings of the International Conference on Data Engineering (ICDE), Cancún, Mexico, April 2008. To appear.
• 2: Nikolaus Augsten , Michael Böhlen , Johann Gamper, Approximate matching of hierarchical data using pq-grams, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 4: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 5: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 6: Sudarshan S. Chawathe , Anand Rajaraman , Hector Garcia-Molina , Jennifer Widom, Change detection in hierarchically structured information, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.493-504, June 04-06, 1996, Montreal, Quebec, Canada
• 7: Weimin Chen, New algorithm for ordered tree-to-tree correction problem, Journal of Algorithms, v.40 n.2, p.135-158, August 2001 [doi>10.1006/jagm.2001.1170]
• 8: Mayur Datar , Nicole Immorlica , Piotr Indyk , Vahab S. Mirrokni, Locality-sensitive hashing scheme based on p-stable distributions, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997857]
• 9: Minos Garofalakis , Amit Kumar, XML stream processing using tree-edit distance embeddings, ACM Transactions on Database Systems (TODS), v.30 n.1, p.279-332, March 2005 [doi>10.1145/1061318.1061326]
• 10: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 11: Sreenivas Gollapudi , Rina Panigrahy, Exploiting asymmetry in hierarchical topic extraction, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183683]
• 12: Taher H. Haveliwala, Aristides Gionis, and Piotr Indyk. Scalable techniques for clustering the web. In WebDB (Informal Proceedings), pages 129--134, 2000.
• 13: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 14: Tao Jiang , Lusheng Wang , Kaizhong Zhang, Alignment of Trees - An Alternative to Tree Edit, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.75-86, June 05-08, 1994
• 15: K. Kailing, H-P. Kriegel, S. Schonauer, and T. Seidl. Efficient similarity search for hierarchical data in large databases. In Proc. 9th Intl Conference on Extending Database Technology, pages 676--693, 2004.
• 16: T. Margush and F. R. McMorris. Consensus n-trees. Bulletin of Mathematical Biology, 3:239--244, 1981.
• 17: Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060623]
• 18: Rina Panigrahy, Entropy based nearest neighbor search in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1186-1195, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109688]
• 19: K. Zhang. A constrained editing distance between unordered labeled trees. Algorithmica, 15:205--222, 1996.
• 20: K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989 [doi>10.1137/0218082]
• 21: Li Zhang. On matching nodes between trees. Technical Report HPL-2003-67, HP Laboratories, Palo Alto, CA, April 2003.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
earth movers distance, locality sensitive hashing, similarity