Similarity evaluation on tree-structured data

ABSTRACT

Tree-structured data are becoming ubiquitous nowadays and manipulating them based on similarity is essential for many applications. The generally accepted similarity measure for trees is the edit distance. Although similarity search has been extensively studied, searching for similar trees is still an open problem due to the high complexity of computing the tree edit distance. In this paper, we propose to transform tree-structured data into an approximate numerical multidimensional vector which encodes the original structure information. We prove that the L1 distance of the corresponding vectors, whose computational complexity is O(|T1| + |T2|), forms a lower bound for the edit distance between trees. Based on the theoretical analysis, we describe a novel algorithm which embeds the proposed distance into a filter-and-refine framework to process similarity search on tree-structured data. The experimental results show that our algorithm reduces dramatically the distance computation cost. Our method is especially suitable for accelerating similarity query processing on large trees in massive datasets.

REFERENCES

• 1: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu, A new method for similarity indexing of market basket data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.407-418, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 3: Edgar Chavez and Gonzalo Navarro. Towards measuring the searching complexity of metric sapces. In Proc. of the Mexican Computing Meeting, pages 969--978, 2001.
• 4: Minos Garofalakis , Amit Kumar, Correlating XML data streams using tree-edit distance embeddings, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.143-154, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773168]
• 5: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 6: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 7: K. Kailing, H. P. Kriegel, S. Schönauer, and T. Seidl. Efficient similarity search for hierarchical data in large databases. In EDBT, pages 676--693, March. 2004.
• 8: Juha Kärkkäinen, Computing the Threshold for q-Gram Filters, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.348-357, July 03-05, 2002
• 9: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 10: Nikos Mamoulis, David W. Cheung, and Wang Lian. Similarity search in sets and categorical data using the signature tree. In ICDE, pages 75--86, 2003.
• 11: Alexandros Nanopoulos , Yannis Manolopoulos, Efficient similarity search for market basket data, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.2, p.138-152, October 2002 [doi>10.1007/s00778-002-0068-7]
• 12: Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
• 13: Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.154-165, June 01-04, 1998, Seattle, Washington, United States
• 14: Stanley M. Selkow. The tree-to-tree editing problem. Information Processing Letters, 6:184--186, December 1977.
• 15: Sudipto Guha , H. V. Jagadish , Nick Koudas , Divesh Srivastava , Ting Yu, Approximate XML joins, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564725]
• 16: Dennis Shasha and Kaizhong Zhang. Approximate Tree Pattern Matching. Oxford University, 1997.
• 17: Erkki Sutinen , Jorma Tarhio, On Using q-Gram Locations in Approximate String Matching, Proceedings of the Third Annual European Symposium on Algorithms, p.327-340, September 25-27, 1995
• 18: 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
• 19: Esko Ukkonen, Approximate string-matching with q-grams and maximal matches, Theoretical Computer Science, v.92 n.1, p.191-211, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90143-4]
• 20: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 21: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775058]
• 22: Kaizhong Zhang. Algorithms for the constrained editing distance between ordered labelled trees and related problems. In Pattern Regonition, volume 28, pages 463--474, 1995.
• 23: 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]