Last updated on 03/11/2021
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
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.