Finding similar consensus between trees: An algorithm and a distance hierarchy

Jason T.L. Wang, Kaizhong Zhang

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

The problem of finding this similar consensus (also known as the largest approximately common substructures) of two trees arises in many pattern recognition applications. This paper presents a dynamic programming algorithm to solve the problem based on the distance measure originated from Tanaka and Tanaka. The algorithm runs as fast as the best-known algorithm for comparing two trees using Tanaka's distance measure when the allowed distance between the common substructures is a constant independent of the input trees. In addition, we establish a hierarchy among Tanaka's distance measure and three other edit-based distance measures published in the literature.

Original languageEnglish (US)
Pages (from-to)127-137
Number of pages11
JournalPattern Recognition
Volume34
Issue number1
DOIs
StatePublished - Jan 2001

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Keywords

  • Computational biology
  • Dynamic programming
  • Edit distance
  • Pattern matching
  • Trees

Fingerprint Dive into the research topics of 'Finding similar consensus between trees: An algorithm and a distance hierarchy'. Together they form a unique fingerprint.

Cite this