2026-07-21T14:18:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8687 2024-03-06T10:43:02Z ddc:004 open_access

Linear-time algorithms for the subpath kernel Shin, Kilho Ishikawa, Taichi tree kernel suffix tree 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kilho Shin and Taichi Ishikawa 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.22 urn:nbn:de:0030-drops-86877 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.22 eng https://creativecommons.org/licenses/by/3.0/legalcode