Fast Kernels for String and Tree Matching

In this paper we present a new algorithm suitable for matching discrete objects such as strings and trees in linear time, thus obviating dynarrtic programming with quadratic time complexity. Furthermore, prediction cost in many cases can be reduced to linear cost in the length of the se(cid: 173) quence to be classified, regardless of the number of support vectors. This improvement on the currently available algorithms makes string kernels a viable alternative for the practitioner.

Authors

• Alex Smola
• S. V. N. Vishwanathan

Keywords

No keywords are indexed for this paper.