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

Jason T.L. Wang, Kaizhong Zhang

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


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
Issue number1
StatePublished - Jan 2001

All Science Journal Classification (ASJC) codes

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


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


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