Abstract
In this paper we present a new algorithm suitable for matching discrete objects such as strings and trees in linear time, thus obviating dynamic programming with quadratic time complexity. Furthermore, prediction cost in many cases can be reduced to linear cost in the length of the sequence 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.
Keywords
Matching (statistics)Tree (set theory)Computer scienceString (physics)String searching algorithmMathematicsArtificial intelligencePattern matchingCombinatoricsStatistics
Affiliated Institutions
Related Publications
A linear space algorithm for computing maximal common subsequences
The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadra...
IQ-TREE: A Fast and Effective Stochastic Algorithm for Estimating Maximum-Likelihood Phylogenies
Large phylogenomics data sets require fast tree inference methods, especially for maximum-likelihood (ML) phylogenies. Fast programs exist, but due to inherent heuristics to fin...
IQPNNI: Moving Fast Through Tree Space and Stopping in Time
An efficient tree reconstruction method (IQPNNI) is introduced to reconstruct a phylogenetic tree based on DNA or amino acid sequence data. Our approach combines various fast al...
Similarity Search in High Dimensions via Hashing
The nearest- or near-neighbor query problems arise in a large variety of database applications, usually in the context of similarity searching. Of late, there has been increasin...
The fragment assembly string graph
Abstract We present a concept and formalism, the string graph, which represents all that is inferable about a DNA sequence from a collection of shotgun sequencing reads collecte...
Publication Info
- Year
- 2004
- Type
- book-chapter
- Pages
- 113-130
- Citations
- 293
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
293
OpenAlex
Cite This
S. V. N. Vishwanathan,
Alexander J. Smola
(2004).
Fast Kernels for String and Tree Matching.
The MIT Press eBooks
, 113-130.
https://doi.org/10.7551/mitpress/4057.003.0008
Identifiers
- DOI
- 10.7551/mitpress/4057.003.0008