Similar subtree search using extended tree inclusion

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

doi:10.1109/ICDE.2016.7498424

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 proceeding › Conference article published in proceeding or book › Academic research › peer-review

Abstract

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 language	English
Title of host publication	2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
Publisher	IEEE
Pages	1558-1559
Number of pages	2
ISBN (Electronic)	9781509020195
DOIs	https://doi.org/10.1109/ICDE.2016.7498424
Publication status	Published - 22 Jun 2016
Externally published	Yes
Event	32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland Duration: 16 May 2016 → 20 May 2016

Conference

Conference	32nd IEEE International Conference on Data Engineering, ICDE 2016
Country/Territory	Finland
City	Helsinki
Period	16/05/16 → 20/05/16

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

More information

10.1109/ICDE.2016.7498424

Cite this

@inproceedings{15e1cbced1f441d6aa7408707626d199,

title = "Similar subtree search using extended tree inclusion",

abstract = "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.",

author = "Tomoya Mori and Atsuhiro Takasu and Jansson, {Jesper Andreas} and Jaewook Hwang and Takeyuki Tamura and Tatsuya Akutsu",

year = "2016",

month = jun,

day = "22",

doi = "10.1109/ICDE.2016.7498424",

language = "English",

pages = "1558--1559",

booktitle = "2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016",

publisher = "IEEE",

address = "United States",

note = "32nd IEEE International Conference on Data Engineering, ICDE 2016 ; Conference date: 16-05-2016 Through 20-05-2016",

}

Similar subtree search using extended tree inclusion. / Mori, Tomoya; Takasu, Atsuhiro; Jansson, Jesper Andreas et al.
2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016. IEEE, 2016. p. 1558-1559 7498424.

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Similar subtree search using extended tree inclusion

AU - Mori, Tomoya

AU - Takasu, Atsuhiro

AU - Jansson, Jesper Andreas

AU - Hwang, Jaewook

AU - Tamura, Takeyuki

AU - Akutsu, Tatsuya

PY - 2016/6/22

Y1 - 2016/6/22

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84980417501&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2016.7498424

DO - 10.1109/ICDE.2016.7498424

M3 - Conference article published in proceeding or book

SP - 1558

EP - 1559

BT - 2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016

PB - IEEE

T2 - 32nd IEEE International Conference on Data Engineering, ICDE 2016

Y2 - 16 May 2016 through 20 May 2016

ER -

Similar subtree search using extended tree inclusion

Abstract

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this