  The kernel method is a potential approach to analyzing structured data such
as sequences, trees, and graphs; however, unordered trees have not been
investigated extensively. Kimura et al. (2011) proposed a kernel function for
unordered trees on the basis of their subpaths, which are vertical
substructures of trees responsible for hierarchical information in them. Their
kernel exhibits practically good performance in terms of accuracy and speed;
however, linear-time computation is not guaranteed theoretically, unlike the
case of the other unordered tree kernel proposed by Vishwanathan and Smola
(2003). In this paper, we propose a theoretically guaranteed linear-time kernel
computation algorithm that is practically fast, and we present an efficient
prediction algorithm whose running time depends only on the size of the input
tree. Experimental results show that the proposed algorithms are quite
efficient in practice.
