Skip navigation
Skip navigation

Fast and space efficient string kernels using suffix arrays

Teo, Choon-Hui; Vishwanathan, S


String kernels which compare the set of all common substrings between two given strings have recently been proposed by Vishwanathan & Smola (2004). Surprisingly, these kernels can be computed in linear time and linear space using annotated suffix trees. Even though, in theory, the suffix tree based algorithm requires O(n) space for an n length string, in practice at least 40n bytes are required - 20n bytes for storing the suffix tree, and an additional 20n bytes for the annotation. This large...[Show more]

CollectionsANU Research Publications
Date published: 2006
Type: Conference paper
Source: Proceedings of 23rd International Conference of Machine Learning
DOI: 10.1145/1143844.1143961


File Description SizeFormat Image
01_Teo_Fast_and_space_efficient_2006.pdf249.57 kBAdobe PDF    Request a copy
02_Teo_Fast_and_space_efficient_2006.pdf565.44 kBAdobe PDF    Request a copy
03_Teo_Fast_and_space_efficient_2006.pdf64.6 kBAdobe PDF    Request a copy
04_Teo_Fast_and_space_efficient_2006.pdf125.78 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  12 November 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator