一种基于LSH的时间子序列匹配查询算法

doi:10.11959/j.issn.1000-0801.2015196

摘要/Abstract

摘要：

提出了一种基于LSH（locality sensitive hashing，局部敏感散列）算法处理时间子序列匹配问题的方法LSHSM。不同于FRM和DualMatch方法，该方法不需要对时间序列做DFT、DWT等特征变换，而是直接把序列看成高维数据点，利用LSH能处理高维数据的特性来查找相似时间子序列。实验采用3种不同的时间序列数据集，通过与线性扫描算法比较，验证了算法的有效性，性能有很大的提高。

关键词: 时间子序列, LSH, 匹配查询

Abstract:

An algorithm called LSHSM，which uses locality sensitive hashing（LSH）to process time subsequence matching，was proposed.Different to the FRM and DualMatch algorithms，the LSHSM does not require feature transformation such as DFT and DWT.It just directly regards the sequence as a high-dimensional object to find similar subsequences.Comparing to a linear algorithm on three real datasets，the LSHSM algorithm demonstrates the effectiveness and efficiency.

Key words: time subsequence, locality sensitive hashing, match searching

刘根平,陈叶芳,杜呈透,钱江波. 一种基于LSH的时间子序列匹配查询算法[J]. 电信科学, 2015, 31(8): 63-71.

Genping Liu,Yefang Chen,Chengtou Du,Jiangbo Qian. An LSH Based Time Subsequence Matching Algorithm[J]. Telecommunications Science, 2015, 31(8): 63-71.

图/表 10

表1

图1

图2

表2

图3

图4

图5

图6

图7

图8

参考文献 27

1	肖辉 . 时间序列的相似性查询与异常检测（博士学位论文）. 复旦大学， 2005 Xiao H . Similarity search and outlier detection in time series （doctor dissertation）. Fudan University， 2005
2	曾海泉 . 时间序列挖掘与相似性查找技术研究（博士学位论文）. 复旦大学， 2003 Zeng H Q . Research on mining and similarity search in time series database（doctor dissertation）. Fudan University， 2003
3	Fu T . review on time series data mining. Engineering Applications of Artificial Intelligence， 2011，24（1）： 164～181
4	Christos F ， Ranganathan M ， Manolopoulos Y . Fast subsequence matching in time-series databases. Proceedings of ACM SIGMOD Conference， Minneapolis，USA， 1994
5	Moon Y S ， Whang K Y ， Loh W K . Duality-based subsequence matching in time-series databases. Proceedings of the 17th International Conference on Data Engineering， Heidelberg，Germany， 2001： 263～272
6	Ruben B ， Homaifar A ， Gebril M ，et al. Satellite image retrieval using low memory locality sensitive hashing in Euclidean space. Earth Science Informatics， 2011，4（1）： 17～28
7	Yi Y ， Michel C ， Vincent O ，et al. Local summarization and multi-level LSH for retrieving multi-variant audio tracks. Proceedings of the 17th ACM International Conference on Multimedia， Beijing，China， 2009： 341～350
8	Paisitkriangkrai S ， Mei T ， Zhang J ，et al. Scalable clip-based near-duplicate video detection with ordinal measure. Proceedings of the ACM International Conference on Image and Video Retrieval， Xi’an，China， 2010： 121～128
9	Zhu L ， Liu T ， Gibbon D ，et al. Effective and scalable video copy detection. Proceedings of the 11th ACM International Conference on Multimedia Information Retrieval， Philadelphia，USA， 2010： 119～128
10	Agrawal R ， Faloutsos C ， Swami A . Efficient similarity search in sequence databases. Proceedings of the 4th International Conference FODO， Chicago，USA， 1993： 69～84
11	Indyk P ， Motwani R ， Swami A . Approximate nearest neighbors：towards removing the curse of dimensionality. Proceedings of the 30th Annual ACM Symposium on Theory of Computing， Dallas，USA， 1998： 604～613
12	Gionis A ， Indyk P ， Motwani R . Similarity search in high dimensions via hashing. Proceedings of the 25th International Conference on Very Large Data Bases（VLDB）， Edinburgh，UK， 1999： 518～529
13	，甘骏豪 . 基于动态碰撞检测的位置敏感哈希（硕士学位论文）. 中山大学， 2013 Gan J H . Locality-sensitive hashing scheme based on dynamic collision counting（master dissertation）. Sun Yat-sen University， 2013
14	Datar M ， Nicole I ， Indyk P ，et al. Locality-sensitive hashing scheme based on p-stable distributions. Proceedings of the 20th Annual Symposium on Computational Geometry， New York，USA， 2004： 253～262
15	Yan K ， Sukthankar R ， Huston L . Efficient near-duplicate detection and sub-image retrieval. ACM Multimedia， 2004，4（1）： 869～876
16	Bogdan M ， Shan Y ， Sawhney H S ，et al. Rapid object indexing using locality sensitive hashing and joint 3D-signature space estimation. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2006，28（7）： 1111～1126
17	Manku G S ， Jain A ， Sarma A D . Detecting near-duplicates for web crawling. Proceedings of the 16th International Conference on World Wide Web， Banff，Alberta，Canada， 2007： 141～150
18	Das A S ， Datar M ， Garg A ，et al. Google news personalization：scalable online collaborative filtering. Proceedings of the 16th International Conference on World Wide Web， Banff，Alberta，Canada， 2007： 271～280
19	Buhler J . Efficient large-scale sequence comparison by locality-sensitive hashing. Bioinformatics， 2001，17（5）： 419～428
20	Buhler J . Provably sensitive indexing strategies for biosequence similarity search. Journal of Computational Biology， 2003，10（3～4）： 399～417
21	Wang Y ， Parthasarathy S ， Tatikonda S . Locality sensitive outlier detection：a ranking driven approach. Proceedings of the IEEE 27th International Conference on Data Engineering（ICDE）， Hannover，Germany， 2011： 410～421
22	Pillutla M R ， Raval N ， Bansal P ，et al. LSH based outlier detection and its application in distributed setting. Proceedings of the 20th ACM International Conference on Information and Knowledge Management， Glasgow，Scotland，UK， 2011： 2289～2292
23	汤春蕾，董家麒 . 基于LSH的时间子序列查询算法. 计算机学报， 2012，35（11）： 2228～2236 Tang C L ， Dong J Q . Similarity query of time series subsequences based on LSH. Chinese Journal of Computers， 2012，35（11）： 2228～2236
24	李俊奎 . 时间序列相似性问题研究（博士学位论文）. 华中科技大学， 2008 Li J K . Research on time series sequence similarity（doctor dissertation）. Huazhong University of Science and Technology， 2008
25	Moon Y S ， Whang K Y ， Han W S . General match：a subsequence matching method in time-series databases based on generalized windows. Proceedings of the ACM SIGMOD International Conference on Management of Data， Madison，Wisconsin，USA， 2002： 382～393
26	Cai Y ， Ng R . Indexing spatio-temporal trajectories with Chebyshev polynomials. Proceedings of the ACM SIGMOD International Conference on Management of Data， Baltimore，Maryland，USA， 2004： 599～610
27	凌康 . 基于位置敏感哈希的相似性搜索技术研究（硕士学位论文）. 南京大学， 2012 Ling K . Research on locality sensitive hashing-based similarity Search（marster dissertation）.. Nanjing University， 2012

符号	含义
MBR	最小边界矩形
Q	查询序列
S	数据库序列
\|Q\|	Q的长度
S_i，j	起始于i、终止于j的S的子序列
s_i	序列S的第i个元素
D（Q，S_i，j）	Q与S_i，j之间的距离

数据集	长度/数据点个数
Walk1M	1 000 000
stock	1 916 833
stock2	3 240 000