Kernel methods are powerful tools in machine learning. They have to be computationally efficient. In this paper, we present a novel list-based approach to compute efficiently the string subsequence kernel (SSK). Our main idea is that our list-based SSK reduces to range query problem. We started by the construction of a match list L(s,t )= {(i,j ): si = tj} where s and t are the strings to be compared; such match list contains only the required data that contribute to the result. To do some intermediate processing efficiently, we constructed a layered range tree and applied the corresponding computational geometry algorithms. Moreover, we extended our match list to be a list of lists in order to improve the computation efficiency of the SSK. The whole process takes O(|L|log |L|+pK) time and O(|L|log |L|+K) space, where |L| is the size of the match list, p is the length of the SSK and K is the total reported points by range queries over all the entries of the list.
['Slimane Bellaouar', 'Hadda Cherroun', 'Djelloul Ziadi']
Efficient List-Based Computation of the String Subsequence Kernel