TY - JOUR
T1 - A System for Approximate Tree Matching
AU - Wang, Jason Tsong Li
AU - Zhang, Kaizhong
AU - Jeong, Karpjoo
AU - Shasha, Dennis
N1 - Funding Information:
Manuscript received February 26, 1991; revised March 12, 1992. This work was supported in part by the National Science Foundation under Grants IRI-8901699 and CCR-9103953, in part by the Office of Naval Research under Grants NOOO14-90-5-11 IO and NOOO14-91-J-1472, in part by the New Jersey lnstitute of Technology under Grant 421280, and in part by the Natural Sciences and Engineering Research Council of Canada under Grant OGP0046373. 1.T.-L. Wang was with the Courant Institute of Mathematical Sciences, New York University, New York, NY 10012 USA. He is now with the Department of Computer and Information Science, New Jersey Institute of Technology, Newark, NJ 07 102 USA; e-mail: [email protected]. K. Zhang is with the Department of Computer Science, Middlesex College, University of Western Ontario, London, ON N6A 5B7 Canada. K. Jeong and D. Shasha are with the Courant Institute of Mathematical Sciences, New York University, New York, NY 10012 USA. IEEE Log Number 9213345.
PY - 1994/8
Y1 - 1994/8
N2 - Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology, programming compilation, and natural language processing. Many of the applications involve comparing trees or retrieving/extracting information from a repository of trees. Examples include classification of unknown patterns, analysis of newly sequenced RNA structures, semantic taxonomy for dictionary definitions, generation of interpreters for nonprocedural programming languages, and automatic error recovery and correction for programming languages. Previous systems use exact matching (or generalized regular expression matching) for tree comparison. This paper presents a system, called Approximate-Tree-By-Example (ATBE), which allows inexact matching of trees. The ATBE system interacts with the user through a simple but powerful query language; graphical devices are provided to facilitate inputing the queries. The paper describes the architecture of ATBE, illustrates its use and describes some aspects of ATBE implementation. We also discuss the underlying algorithms and provide some sample applications.
AB - Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology, programming compilation, and natural language processing. Many of the applications involve comparing trees or retrieving/extracting information from a repository of trees. Examples include classification of unknown patterns, analysis of newly sequenced RNA structures, semantic taxonomy for dictionary definitions, generation of interpreters for nonprocedural programming languages, and automatic error recovery and correction for programming languages. Previous systems use exact matching (or generalized regular expression matching) for tree comparison. This paper presents a system, called Approximate-Tree-By-Example (ATBE), which allows inexact matching of trees. The ATBE system interacts with the user through a simple but powerful query language; graphical devices are provided to facilitate inputing the queries. The paper describes the architecture of ATBE, illustrates its use and describes some aspects of ATBE implementation. We also discuss the underlying algorithms and provide some sample applications.
KW - Editing distance
KW - graphics
KW - pattern matching
KW - query language
KW - query processing
KW - tool
KW - tree comparison
KW - trees
UR - http://www.scopus.com/inward/record.url?scp=0028485693&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028485693&partnerID=8YFLogxK
U2 - 10.1109/69.298173
DO - 10.1109/69.298173
M3 - Article
AN - SCOPUS:0028485693
SN - 1041-4347
VL - 6
SP - 559
EP - 571
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 4
ER -