Subsequence query technique has important applications in several fields such as finance, commerce and healthcare. However, due to the high time complexity of similarity comparison algorithms such as dynamic time warping(DTW), the length of subsequence has a great influence on the retrieval time, which limits the efficiency of long subsequence retrieval on data sets. This paper proposed a fast subsequence query algorithm based on short sequence grouping and assembling strategy. This algorithm first separated all subsequences which were in a given length in the data set into groups and marked out the representative subsequence for each group. Then it cut the query sequence into small query sequences with a fixed length during the query processing, and used DTW algorithm to compute the candidate sets of subsequences. The representative subsequence had a high similarity with the small query sequences. Finally, it assembled all the sequences in the candidate sets to derive the query result sequences. Experiments show that the efficiency of the new algorithm is about 10 times higher than that of the typical algorithm.

[2020-06-05] Printed Article /doc/2018.11.0866/v2