期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种基于LSH的时间子序列匹配查询算法 被引量：1

An LSH Based Time Subsequence Matching Algorithm
下载PDF
导出
摘要 提出了一种基于LSH(locality sensitive hashing,局部敏感散列)算法处理时间子序列匹配问题的方法LSHSM。不同于FRM和Dual Match方法 ,该方法不需要对时间序列做DFT、DWT等特征变换,而是直接把序列看成高维数据点,利用LSH能处理高维数据的特性来查找相似时间子序列。实验采用3种不同的时间序列数据集,通过与线性扫描算法比较,验证了算法的有效性,性能有很大的提高。 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.
作者 刘根平 陈叶芳 杜呈透 钱江波
机构地区 宁波大学信息科学与工程学院
出处 《电信科学》 北大核心 2015年第8期63-71,共9页 Telecommunications Science
基金 国家自然科学基金资助项目(No.61472194) 浙江省自然科学基金资助项目(No.LY13F020040) 宁波市自然科学基金资助项目(No.2014A610023 No.2015A610119) "信息与通信工程"浙江省重中之重学科开放基金资助项目~~
关键词 时间子序列 LSH 匹配查询 time subsequence, locality sensitive hashing, match searching
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献22

  • 1Fu T. A review on time series data mining. Engineering Applications of Artificial Intelligence, 2011, 24(1): 164-181.
  • 2Christos F, Ranganathan M, Manolopoulos Y. Fast subsequence matching in time-series databases. Proceedings of ACM SIGMOD Conference, Minneapolis, USA, 1994.
  • 3Moon 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.
  • 4Ruben B, Homaifar A, Gebril M, et al. Satellite image retrieval using low memory locality sensitive hashing in Euclidean space. Earth Science Informatics, 2011, g(1): 17-28.
  • 5Yi Y, Michel C, Vincent O, et d. 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.
  • 6Paisitkriangkrai S, Mei T, Zhang J, et ol. Scalable clip-based near-duplicate video detection with ordinal measure. Proceedings of the ACM International Conference on Image and VideoRetrieval, Xi'an, China, 2010:121-128.
  • 7Zhu L, Liu T, Gibbon D, et ol. Effective and scalable video copy detection. Proceedings of the 11th ACM International Conference on Multimedia Information Retrieval, Philadelphia, USA, 2010:119-128.
  • 8Agrawal R, Faloutsos C, Swami A. Efficient similarity search in sequence databases. Proceedings of the 4th International Conference FODO, Chicago, USA, 1993:69-84.
  • 9Indyk P, Motwani R. 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.
  • 10Gionis 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.

二级参考文献20

  • 1Keogh E. Exact indexing of dynamic time warping//Proceed- ings of the VLDB. Hong Kong, China, 2002: 406-417.
  • 2Rafiei D, Mendelzon A O. Querying time series data based on similarity. IEEE Transactions on Knowledge and Data Engineering, 2000, 12(5): 675-693.
  • 3Berndt D, Clifford J. Finding patterns in time series: A dynamic programming approach//Advances in Knowledge Discovery and Data Mining. American Association for Artificial Intelligence. Menlo Park, CA, USA, 1996:229-248.
  • 4Sakoe H, Chiba S. Dynamic programming algorithm optimi- zation for spoken word recognition. IEEE Transactions on ASSP, 1978, 26(1): 43-49.
  • 5Vlachos M, Gunopulos D, Kollios G. Discovering similar multi-dimensional trajectories//Proceedings of the ICDE. San Jose, CA, USA, 2002:673-684.
  • 6Chen L, Ozsu M T, Oria V. Robust and fast similarity search for moving object trajectories//Proceedings of the 2005 ACM SIGMOD International Conference on Manage- ment of Data. New York, USA, 2005: 491-502.
  • 7Chen L, Ng R T. On the marriage of Lp-norms and edit dis- tance//Proceedings of the 30th International Conference on Very Large Data Bases. 2004:792-803.
  • 8Agrawal R, Faloutsos C, Swami A. Efficient similarity search in sequence databases//Proceedings of the FODO. Chicago, Illinois, USA, 1993:69-84.
  • 9Beckmann Net al. The R.tree: An efficient and robust access method for points and rectangles//Proceedings of the SIGMOD. Atlantic City, NJ, USA, 1990:322-331.
  • 10Keogh E et al. Locally adaptive dimensionality reduction for indexing large time series databases//Proceedings of the SIGMOD. Santa Barbara, CA, USA, 2001:151-162.

共引文献5

同被引文献3

引证文献1

二级引证文献5

电信科学
2015年 第8期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部