Similar Subtree Search Using Extended Tree Inclusion

Tomoya Mori, Atsuhiro Takasu, Jesper Andreas Jansson, Jaewook Hwang, Takeyuki Tamura, Tatsuya Akutsu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

This paper considers the problem of identifying all locations of subtrees in a large tree or in a large collection of trees that are similar to a specified pattern tree, where all trees are assumed to be rooted and node-labeled. The tree edit distance is a widely-used measure of tree (dis-)similarity, but is NP-hard to compute for unordered trees. To cope with this issue, we propose a new similarity measure which extends the concept of unordered tree inclusion by taking the costs of insertion and substitution operations on the pattern tree into account, and present an algorithm for computing it. Our algorithm has the same time complexity as the original one for unordered tree inclusion, i.e., it runs in O(/T1//T2/) time, where T1 and T2 denote the pattern tree and the text tree, respectively, when the maximum outdegree of T1 is bounded by a constant. Our experimental evaluation using synthetic and real datasets confirms that the proposed algorithm is fast and scalable and very useful for bibliographic matching, which is a typical entity resolution problem for tree-structured data. Furthermore, we extend our algorithm to also allow a constant number of deletion operations on T1 while still running in O(/T1//T2/) time.
Original languageEnglish
Article number7161364
Pages (from-to)3360-3373
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume27
Issue number12
DOIs
Publication statusPublished - 1 Dec 2015
Externally publishedYes

Keywords

  • dynamic programming
  • Tree edit distance
  • tree inclusion
  • unordered trees

ASJC Scopus subject areas

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

Cite this