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

刘根平; 陈叶芳; 杜呈透; 钱江波

doi:10.11959/j.issn.1000-0801.2015196

您当前的位置：

首页 >

文章列表页 >

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

研究与开发 | 更新时间：2024-06-05

- 一种基于LSH的时间子序列匹配查询算法
- An LSH Based Time Subsequence Matching Algorithm
- 电信科学 2015年31卷第8期页码：63-71
- 作者机构：
- 作者简介：
  
  [ "刘根平，女，宁波大学信息科学与工程学院硕士生，主要研究方向为数据流处理和挖掘。" ]
  [ "陈叶芳，女，宁波大学信息科学与工程学院讲师，主要研究方向为数据处理和挖掘。" ]
  [ "杜呈透，男，宁波大学信息科学与工程学院副教授，主要研究方向为数据处理和挖掘。" ]
  [ "钱江波，男，博士，宁波大学信息科学与工程学院教授，主要研究方向为数据处理和挖掘、逻辑电路设计。" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61472194);浙江省自然科学基金资助项目;The Natural Science Foundation of Zhejiang Province(LY13F020040);宁波市自然科学基金资助项目;The Natural Science Foundation of Ningbo City(2014A610023);宁波市自然科学基金资助项目;The Natural Science Foundation of Ningbo City(2015A610119);“信息与通信工程”浙江省重中之重学科开放基金资助项目;Zhejiang Key Discipline Fund of Information and Communication Engineering
- DOI：10.11959/j.issn.1000-0801.2015196
  中图分类号：
- 网络出版日期：2015-08，
  
  纸质出版日期：2015-08-20
- 稿件说明：
移动端阅览
刘根平, 陈叶芳, 杜呈透, 等. 一种基于LSH的时间子序列匹配查询算法[J]. 电信科学, 2015,31(8):63-71.

Genping Liu, Yefang Chen, Chengtou Du, et al. An LSH Based Time Subsequence Matching Algorithm[J]. Telecommunications science, 2015, 31(8): 63-71.
刘根平, 陈叶芳, 杜呈透, 等. 一种基于LSH的时间子序列匹配查询算法[J]. 电信科学, 2015,31(8):63-71. DOI： 10.11959/j.issn.1000-0801.2015196.

Genping Liu, Yefang Chen, Chengtou Du, et al. An LSH Based Time Subsequence Matching Algorithm[J]. Telecommunications science, 2015, 31(8): 63-71. DOI： 10.11959/j.issn.1000-0801.2015196.

摘要

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

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.

关键词

Keywords

references

肖辉 . 时间序列的相似性查询与异常检测（博士学位论文） . 复旦大学， 2005

Xiao H . Similarity search and outlier detection in time series （doctor dissertation） . Fudan University ， 2005

曾海泉 . 时间序列挖掘与相似性查找技术研究（博士学位论文） . 复旦大学， 2003

Zeng H Q . Research on mining and similarity search in time series database（doctor dissertation） . Fudan University ， 2003

Fu T . review on time series data mining . Engineering Applications of Artificial Intelligence ， 2011 ， 24 （ 1 ）： 164 ～ 181

Christos F ， Ranganathan M ， Manolopoulos Y . Fast subsequence matching in time-series databases . Proceedings of ACM SIGMOD Conference ， Minneapolis，USA ， 1994

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

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

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

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

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

Agrawal R ， Faloutsos C ， Swami A . Efficient similarity search in sequence databases . Proceedings of the 4th International Conference FODO ， Chicago，USA ， 1993 ： 69 ～ 84

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

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

，甘骏豪 . 基于动态碰撞检测的位置敏感哈希（硕士学位论文） . 中山大学， 2013

Gan J H . Locality-sensitive hashing scheme based on dynamic collision counting（master dissertation） . Sun Yat-sen University ， 2013

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

Yan K ， Sukthankar R ， Huston L . Efficient near-duplicate detection and sub-image retrieval . ACM Multimedia ， 2004 ， 4 （ 1 ）： 869 ～ 876

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

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

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

Buhler J . Efficient large-scale sequence comparison by locality-sensitive hashing . Bioinformatics ， 2001 ， 17 （ 5 ）： 419 ～ 428

Buhler J . Provably sensitive indexing strategies for biosequence similarity search . Journal of Computational Biology ， 2003 ， 10 （ 3 ～ 4 ）： 399 ～ 417

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

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

汤春蕾，董家麒 . 基于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

李俊奎 . 时间序列相似性问题研究（博士学位论文） . 华中科技大学， 2008

Li J K . Research on time series sequence similarity（doctor dissertation） . Huazhong University of Science and Technology ， 2008

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

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

凌康 . 基于位置敏感哈希的相似性搜索技术研究（硕士学位论文） . 南京大学， 2012

Ling K . Research on locality sensitive hashing-based similarity Search（marster dissertation）. . Nanjing University ， 2012

浏览量

1027

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据