Similarity Query of Time Series Sub-Sequences Based on LSH


Tang C. (first author). 2012. “Similarity Query of Time Series Sub-Sequences Based on LSH.” Jisuanji Xuebao (Chinese Journal of Computers), 11, 35, Pp. 2228-2236. Publisher's Version
LSH.pdf654 KB


Subsequence similarity query is an important operation in time series, including range query and k nearest neighbor query. Most of these algorithms are based on the Euclidean distance or DTW distance, weak point of which is the time inefficiencies. We propose a new distance measure based on locality sensitive hash (LSH), which improve the efficiency greatly while ensuring the quality of the query results. We also propose an index structure named DS-Index. Using DS-Index, we prune the candidates of query and thus propose two optimal algorithms: OLSH-Range and OLSH-kNN. Our experiments conducted on real stock exchange transaction sequence datasets show that algorithms can quickly and accurately find similarity query results.

This paper awaraed Sa, Shixuan Best Student Paper at the 29th National Database Conference of China in 2012.

Last updated on 03/11/2021