Algorithmics and applications of tree and graph searching

ABSTRACT

Modern search engines answer keyword-based queries extremely efficiently. The impressive speed is due to clever inverted index structures, caching, a domain-independent knowledge of strings, and thousands of machines. Several research efforts have attempted to generalize keyword search to keytree and keygraph searching, because trees and graphs have many applications in next-generation database systems. This paper surveys both algorithms and applications, giving some emphasis to our own work.

REFERENCES

• 1: Serge Abiteboul, Querying Semi-Structured Data, Proceedings of the 6th International Conference on Database Theory, p.1-18, January 08-10, 1997
• 2: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 3: S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. L. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, 1(1):68-88,1997.
• 4: Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Journal of Computer and System Sciences, v.58 n.3, p.428-452, June 1999 [doi>10.1006/jcss.1999.1627 ]
• 5: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 6: H. A. Almohamad , S. O. Duffuaa, A Linear Programming Approach for the Weighted Graph Matching Problem, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.5, p.522-525, May 1993 [doi>10.1109/34.211474 ]
• 7: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 8: Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.497-508, May 21-24, 2001, Santa Barbara, California, United States
• 9: Sihem Amer-Yahia , SungRan Cho , Divesh Srivastava, Tree Pattern Relaxation, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.496-513, March 25-27, 2002
• 10: R. A. Baeza-Yates, Algorithms for string searching, ACM SIGIR Forum, v.23 n.3-4, p.34-58, Spring 1989 [doi>10.1145/74697.74700]
• 11: Ricardo A. Baeza-Yates , Gaston H. Gonnet, Fast text searching for regular expressions or automaton searching on tries, Journal of the ACM (JACM), v.43 n.6, p.915-936, Nov. 1996 [doi>10.1145/235809.235810]
• 12: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 13: D. Barbosa, A. Barta, A. O. Mendelzon, G. A. Mihaila, F. Rizzolo, and P. Rodriguez-Guianolli. ToX - The Toronto XML engine. In Proceedings of the Workshop on Information Integration on the Web, pages 66-73, 2001.
• 14: H. Barrow and R. M. Burstall. Subgraph isomorphism, matching relational structures and maximal cliques. Information Processing Letters, 4:83-84, 1976.
• 15: S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu, J. Robie, J. Simeon, and M. Stefanescu. XQuery 1.0: An XML Query Language; available at http://www.w3.org/TR/xquery/.
• 16: Peter Buneman, Semistructured data, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-121, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263675]
• 17: Peter Buneman , Susan Davidson , Gerd Hillebrand , Dan Suciu, A query language and optimization techniques for unstructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.505-516, June 04-06, 1996, Montreal, Quebec, Canada
• 18: Peter Buneman , Wenfei Fan , Scott Weinstein, Path constraints on semistructured and structured data, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.129-138, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275502]
• 19: Peter Buneman , Mary Fernandez , Dan Suciu, UnQL: a query language and algebra for semistructured data based on structural recursion, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.1, p.76-110, March 2000 [doi>10.1007/s007780050084]
• 20: H. Bunke, Error Correcting Graph Matching: On the Influence of the Underlying Cost Function, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.9, p.917-922, September 1999 [doi>10.1109/34.790431 ]
• 21: H. Bunke and G. Allermann. Inexact graph matching for structural pattern recognition. Pattern Recognition Letters, 1(4):245-253, 1983.
• 22: Sudarshan S. Chawathe , Serge Abiteboul , Jennifer Widom, Representing and Querying Changes in Semistructured Data, Proceedings of the Fourteenth International Conference on Data Engineering, p.4-13, February 23-27, 1998
• 23: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 24: 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
• 25: Zhiyuan Chen , H. V. Jagadish , Flip Korn , Nick Koudas , S. Muthukrishnan , Raymond T. Ng , Divesh Srivastava, Counting Twig Matches in a Tree, Proceedings of the 17th International Conference on Data Engineering, p.595-604, April 02-06, 2001
• 26: Zhiyuan Chen , Nick Koudas , Flip Korn , S. Muthukrishnan, Selectively estimation for Boolean queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.216-225, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335225]
• 27: William J. Christmas , Josef Kittler , Maria Petrou, Structural Matching in Computer Vision Using Probabilistic Relaxation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.749-764, August 1995 [doi>10.1109/34.400565 ]
• 28: Richard Cole , Ramesh Hariharan , Piotr Indyk, Tree pattern matching and subset matching in deterministic O(n log3 n)-time, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.245-254, January 17-19, 1999, Baltimore, Maryland, United States
• 29: Mariano P. Consens , Alberto O. Mendelzon, GraphLog: a visual formalism for real life recursion, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.404-416, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298591]
• 30: D. J. Cook and L. B. Holder. Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research, 1:231-255, 1994.
• 31: L. P. Cordella , P. Foggia , C. Sansone , M. Vento, An Efficient Algorithm for the Inexact Matching of ARG Graphs Using a Contextual Transformational Model, Proceedings of the International Conference on Pattern Recognition (ICPR '96) Volume III-Volume 7276, p.180, August 25-29, 1996
• 32: D. G. Corneil , C. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism, Journal of the ACM (JACM), v.17 n.1, p.51-64, Jan. 1970 [doi>10.1145/321556.321562]
• 33: L. Dehaspe, H. Toivonen, and R. D. King. Finding frequent substructures in chemical compounds. In Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, pages 30-36, 1998.
• 34: Alin Deutsch , Mary Fernandez , Daniela Florescu , Alon Levy , Dan Suciu, A query language for XML, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1155-1169, May 17, 1999
• 35: Surnjani Djoko , Diane J. Cook , Lawrence B. Holder, An Empirical Study of Domain Knowledge and Its Benefits to Substructure Discovery, IEEE Transactions on Knowledge and Data Engineering, v.9 n.4, p.575-586, July 1997 [doi>10.1109/69.617051 ]
• 36: M. A. Eshera and K.-S. Fu. A graph distance measure for image analysis. IEEE Transactions on Systems, Man, and Cybernetics, 14(3):353-363, 1984.
• 37: J. Feng, M. Laumy, and M. Dhome. Inexact matching using neural networks. In E. Gelsema and L. N. Kanal, editors, Pattern Recognition in Practice IV: Multiple Paradigms, Comparative Studies and Hybrid Systems. North-Holland, 1994.
• 38: Mary Fernández , Daniela Florescu , Jaewoo Kang , Alon Levy , Dan Suciu, Catching the boat with Strudel: experiences with a Web-site management system, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.414-425, June 01-04, 1998, Seattle, Washington, United States
• 39: Mirtha-Lina Fernández , Gabriel Valiente, A graph distance metric combining maximum common subgraph and minimum common supergraph, Pattern Recognition Letters, v.22 n.6-7, p.753-758, May 2001 [doi>10.1016/S0167-8655(01)00017-4 ]
• 40: Alfredo Ferro , Giovanni Gallo , Rosalba Giugno , Alfredo Pulvirenti, Best-Match Retrieval for Structured Images, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.7, p.707-718, July 2001 [doi>10.1109/34.935845 ]
• 41: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 42: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 43: Steven Gold , Anand Rangarajan, A Graduated Assignment Algorithm for Graph Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.4, p.377-388, April 1996 [doi>10.1109/34.491619 ]
• 44: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 45: Gaston H. Gonnet , Frank Wm. Tompa, Mind Your Grammar: a New Approach to Modelling Text, Proceedings of the 13th International Conference on Very Large Data Bases, p.339-346, September 01-04, 1987
• 46: Ralf Hartmut Güting, GraphDB: Modeling and Querying Graphs in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.297-308, September 12-15, 1994
• 47: Marc Gyssens , Jan Paredaens , Dirk van Gucht, A graph-oriented object database model, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.417-424, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298593]
• 48: T. Henderson, Discrete relaxation techniques, Oxford University Press, Inc., New York, NY, 1989
• 49: Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
• 50: R. Horaud , T. Skordas, Stereo Correspondence Through Feature Grouping and Maximal Cliques, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.11, p.1168-1180, November 1989 [doi>10.1109/34.42855 ]
• 51: J. Jaakkola and P. Kilpelainen, Using sgrep for querying structured text files. University of Helsinki, Department of Computer Science, Report C-1996-83, November 1996; available at http://www.cs.helsinki. fi/u/jjaakkol/sgrep.html.
• 52: H. V. Jagadish , Olga Kapitskaia , Raymond T. Ng , Divesh Srivastava, Multi-Dimensional Substring Selectivity Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.387-398, September 07-10, 1999
• 53: H. V. Jagadish , Laks V. S. Lakshmanan , Tova Milo , Divesh Srivastava , Dimitra Vista, Querying network directories, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.133-144, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 54: H. V. Jagadish , Raymond T. Ng , Divesh Srivastava, Substring selectivity estimation, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.249-260, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304001]
• 55: C. A. James, D. Weininger, and J. Delany. Daylight Theory Manual-Daylight 4.71. Daylight Chemical Information Systems, www.daylight.com, 2000.
• 56: Yaron Kanza , Yehoshua Sagiv, Flexible queries over semistructured data, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.40-51, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375558]
• 57: P. Kilpelainen. Tree matching problems with applications to structured text databases. Report A-1992-6, University of Helsinki, Finland, 1992.
• 58: Pekka Kilpeläinen , Heikki Mannila, Retrieval from hierarchical texts by partial patterns, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.214-222, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160722]
• 59: Pekka Kilpeläinen , Heikki Mannila, Query Primitives for Tree-Structured Data, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.213-225, June 05-08, 1994
• 60: Pekka Kilpelainen , Heikki Mannila, Ordered and Unordered Tree Inclusion, SIAM Journal on Computing, v.24 n.2, p.340-356, April 1995 [doi>10.1137/S0097539791218202]
• 61: P. Krishnan , Jeffrey Scott Vitter , Bala Iyer, Estimating alphanumeric selectivity in the presence of wildcards, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.282-293, June 04-06, 1996, Montreal, Quebec, Canada
• 62: Theodore W. Leung , Gail Mitchell , Bharathi Subramanian , Bennet Vance , Scott L. Vandenberg , Stanley B. Zdonik, The AQUA Data Model and Algebra, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.157-175, August 30-September 01, 1993
• 63: G. Levi. A note on the derivation of maximal common subgraphs of two directed or undirected graphs. Calcols, 9:341-354, 1972.
• 64: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 65: Josep Lladoós , Enric Martí , Juan Josée Villanueva, Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.10, p.1137-1143, October 2001 [doi>10.1109/34.954603 ]
• 66: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 67: Sebastian Maneth , Frank Neven, Structured Document Transformations Based on XSL, Revised Papers from the 7th International Workshop on Database Programming Languages: Research Issues in Structured and Semistructured Database Programming, p.80-98, September 01-03, 1999
• 68: Nitish Manocha , Diane J. Cook , Lawrence B. Holder, Structural Web Search Using a Graph-Based Discovery System, Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference, p.133-137, May 21-23, 2001
• 69: Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
• 70: A. O. Mendelzon, G. A. Mihaila, and T. Milo. Querying the World Wide Web. International Journal on Digital Libraries, 1(1):54-67, 1997.
• 71: Alberto O. Mendelzon , Peter T. Wood, Finding Regular Simple Paths in Graph Databases, SIAM Journal on Computing, v.24 n.6, p.1235-1258, Dec. 1995 [doi>10.1137/S009753979122370X]
• 72: Gerome Miklau , Dan Suciu, Containment and equivalence for an XPath fragment, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543623]
• 73: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 74: Sung H. Myaeng , Aurelio Lopez-Lopez, Conceptual graph matching: a flexible algorithm and experiments, International Journal of Pattern Recognition and Artificial Intelligence, v.4 n.2, p.107-126, April–June 1992
• 75: Richard Myers , Richard C. Wilson , Edwin R. Hancock, Bayesian Graph Edit Distance, Proceedings of the 10th International Conference on Image Analysis and Processing, p.1166, September 27-29, 1999
• 76: National Cancer Institute. http://www.nci.nih.gov/.
• 77: Svetlozar Nestorov , Jeffrey D. Ullman , Janet L. Wiener , Sudarshan S. Chawathe, Representative Objects: Concise Representations of Semistructured, Hierarchial Data, Proceedings of the Thirteenth International Conference on Data Engineering, p.79-90, April 07-11, 1997
• 78: Frank Neven , Thomas Schwentick, Expressive and efficient pattern languages for tree-structured data (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.145-156, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335217]
• 79: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 80: W. H. Piel, M. J. Donoghue, and M. J. Sanderson. TreeBASE: A database of phylogenetic information. In Proceedings of the 2nd International Workshop of Species 2000, Tsukuba, Japan, 2000.
• 81: R. Ramesh , I. V. Ramakrishnan, Nonlinear pattern matching in trees, Journal of the ACM (JACM), v.39 n.2, p.295-316, April 1992 [doi>10.1145/128749.128752]
• 82: A. Sanfeliu and K. Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics, 13(3):353-362, 1983.
• 83: T. Schlieder and F. Naumann, Approximate tree embedding for querying XML data. In Proceedings of the ACM SIGIR Workshop on XML and Information Retrieval, Athens, Greece, July 2000.
• 84: D. Shasha, J. T. L. Wang, H. Shan, and K. Zhang. ATreeGrep: Approximate searching in unordered trees. Submitted, 2002.
• 85: Hong Su , Harumi Kuno , Elke A. Rundensteiner, Automating the transformation of XML documents, Proceedings of the 3rd international workshop on Web information and data management, November 09-01, 2001, Atlanta, Georgia, USA [doi>10.1145/502932.502946]
• 86: Bharathi Subramanian , Theodore W. Leung , Scott L. Vandenberg , Stanley B. Zdonik, The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases, Proceedings of the Eleventh International Conference on Data Engineering, p.80-89, March 06-10, 1995
• 87: Bharathi Subramanian , Stanley B. Zdonik , Theodore W. Leung , Scott L. Vandenberg, Ordered Types in the AQUA Data Model, Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, p.115-135, August 30-September 01, 1993
• 88: Dan Suciu, An overview of semistructured data, ACM SIGACT News, v.29 n.4, p.28-38, Dec. 1998 [doi>10.1145/306198.306204]
• 89: W. H. Tsai and K. S. Fu. Error-correcting isomorphism of attributed relational graphs for pattern analysis. IEEE Transactions on Systems, Man, and Cybernetics, 9:757-768, 1979.
• 90: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 91: S. Umeyama, An Eigendecomposition Approach to Weighted Graph Matching Problems, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.5, p.695-703, September 1988 [doi>10.1109/34.6778 ]
• 92: Victor Vianu, A Web Odyssey: from Codd to XML, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-15, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375554]
• 93: J. T. -L. Wang , K. Zhang , K. Jeong , D. Shasha, A System for Approximate Tree Matching, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.559-571, August 1994 [doi>10.1109/69.298173 ]
• 94: Jason T. Wang , Dennis Elliott Shasha , Bruce A. Shapiro, Pattern Discovery in Biomolecular Data: Tools, Techniques, and Applications, Oxford University Press, 1999
• 95: J. T. L. Wang, B. A. Shapiro, D. Shasha, K. Zhang, and C.-Y. Chang. Automated discovery of active motifs in multiple RNA secondary structures. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, pages 70-75, 1996.
• 96: Jason Tsong-Li Wang , Dennis Shasha , George J. S. Chang , Liam Relihan , Kaizhong Zhang , Girish Patel, Structural matching and discovery in document databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.560-563, May 11-15, 1997, Tucson, Arizona, United States
• 97: J. T. L. Wang, K. Zhang, G. Chang, and D. Shasha. Finding approximate patterns in undirected acyclic graphs. Pattern Recognition, 35(2):473-483, 2002.
• 98: J. T. L. Wang, K. Zhang, and G.-W. Chirn. The approximate graph matching problem. In Proceedings of the International Conference on Pattern Recognition, volume 2, pages 284-288, 1994.
• 99: Min Wang , Jeffrey Scott Vitter , Balakrishna R. Iyer, Selectivity Estimation in the Presence of Alphanumeric Correlations, Proceedings of the Thirteenth International Conference on Data Engineering, p.169-180, April 07-11, 1997
• 100: X. Wang, J. T. L. Wang, D. Shasha, B. A. Shapiro, S. Dikshitulu, I. Rigoutsos, and K. Zhang. Automated discovery of active motifs in three dimensional molecules. In Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, pages 89-95, 1997.
• 101: Richard C. Wilson , Edwin R. Hancock, A Bayesian compatibility model for graph matching, Pattern Recognition Letters, v.17 n.3, p.263-276, March 6, 1996 [doi>10.1016/0167-8655(95)00115-8 ]
• 102: A. Wong and M. You. Entropy and distance of random graphs with application to structural pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 7(5):599-609, 1985.
• 103: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
• 104: XML TreeDiff. http://www.alphaworks.ibm.com/aw.nsf/FAQs/xmltreediff.
• 105: Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298576]
• 106: Kaizhong Zhang , Dennis Shasha , Jason T. L. Wang, Approximate tree matching in the presence of variable length don't cares, Journal of Algorithms, v.16 n.1, p.33-66, Jan. 1994 [doi>10.1006/jagm.1994.1003 ]
• 107: Kaizhong Zhang , Rick Statman , Dennis Shasha, On the editing distance between unordered labeled trees, Information Processing Letters, v.42 n.3, p.133-139, May 25, 1992 [doi>10.1016/0020-0190(92)90136-J ]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Theory