基于LSH的时间子序列查询算法  

Similarity Query of Time Series Sub-sequences Based on LSH

作　　者：汤春蕾[1] 董家麒[1] 

机构地区：[1]复旦大学计算机科学技术学院,上海200433

出　　处：《计算机学报》2012年第11期2228-2236,共9页Chinese Journal of Computers

基　　金：上海市重点学科建设基金(B114)资助~~

摘　　要：子序列的相似性查询是时间序列数据集中的一种重要操作,包括范围查询和k近邻查询.现有的大多算法是基于欧几里德距离或者DTW距离的,缺点在于查询效率低下.文中提出了一种新的基于LSH的距离度量方法,可以在保证查询结果质量的前提下,极大提高相似性查询的效率;在此基础上,给出一种DS-Index索引结构,利用距离下界进行剪枝,进而还提出了两种优化的OLSH-Range和OLSH-kNN算法.实验是在真实的股票序列集上进行的,数据结果表明算法能快速精确地找出相似性查询结果.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 Euclidean distance or DTW distance, weak point of which is the time inefficiencies. We propose a new distance meas- ure, based on Locality Sensitive Hash （LSH）, which improve the efficiency greatly while ensu- ring 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.

关 键 词：相似性查询 时间序列数据库 子序列 LSH 索引 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]