Similar subtree search using extended tree inclusion

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


In this paper, we have extended the concept of unordered tree inclusion to take the costs of insertions and substitutions into account. The resulting algorithm, MinCostIncl, has the same time complexity as the original algorithm of [4] for unordered tree inclusion (O(22Dmn)). Computational experiments on a large synthetic dataset as well as real datasets showed that our proposed algorithm is fast and scalable. Source codes of the implemented algorithms are available upon request.
Original languageEnglish
Title of host publication2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
Number of pages2
ISBN (Electronic)9781509020195
Publication statusPublished - 22 Jun 2016
Externally publishedYes
Event32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland
Duration: 16 May 201620 May 2016


Conference32nd IEEE International Conference on Data Engineering, ICDE 2016

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management

Cite this