A System for Approximate Tree Matching

Jason Tsong Li Wang, Kaizhong Zhang, Karpjoo Jeong, Dennis Shasha

Research output: Contribution to journalArticle

88 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)559-571
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume6
Issue number4
DOIs
StatePublished - Aug 1994

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Editing distance
  • graphics
  • pattern matching
  • query language
  • query processing
  • tool
  • tree comparison
  • trees

Cite this