License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.22
URN: urn:nbn:de:0030-drops-86877
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8687/
Shin, Kilho ;
Ishikawa, Taichi
Linear-time algorithms for the subpath kernel
Abstract
The subpath kernel is a useful positive definite kernel, which takes arbitrary rooted trees as input, no matter whether they are ordered or unordered, We first show that the subpath kernel can exhibit excellent classification performance in combination with SVM through an intensive experiment. Secondly, we develop a theory of irreducible trees, and then, using it as a rigid mathematical basis, reconstruct a bottom-up linear-time algorithm for the subtree kernel, which is a correction of an algorithm well-known in the literature. Thirdly, we show a novel top-down algorithm, with which we can realize a linear-time parallel-computing algorithm to compute the subpath kernel.
BibTeX - Entry
@InProceedings{shin_et_al:LIPIcs:2018:8687,
author = {Kilho Shin and Taichi Ishikawa},
title = {{Linear-time algorithms for the subpath kernel}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {22:1--22:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-074-3},
ISSN = {1868-8969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8687},
URN = {urn:nbn:de:0030-drops-86877},
doi = {10.4230/LIPIcs.CPM.2018.22},
annote = {Keywords: tree, kernel, suffix tree}
}
|
Keywords: |
|
tree, kernel, suffix tree |
|
Collection: |
|
Annual Symposium on Combinatorial Pattern Matching (CPM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
18.05.2018 |
