高效时序相似搜索技术  

Underlying Techniques of Efficient Similarity Search on Time Series

作　　者：冯玉才[1] 蒋涛[1] 李国徽[1] 朱虹[1] 

机构地区：[1]华中科技大学计算机科技与技术学院,武汉430074

出　　处：《计算机学报》2009年第11期2107-2122,共16页Chinese Journal of Computers

基　　金：国家"八六三"高技术研究发展计划项目基金(2007AA01Z309;2006AA01Z430);国土资源部三峡库区三期地质灾害防治重大科研专项基金(SXKY3-6-3)资助

摘　　要：时序相似搜索被认为是将来最有前途的技术之一.然而,时序数据是典型的高维海量数据,如何开发高效算法非常关键.文中概述了时序相似搜索技术的研究现状和进展以及研究的主要内容,讨论了该技术的几个重要应用范例,并对一些典型算法进行了定量分析;然后重点论述了高效时序相似搜索的关键技术,包括边界过滤、三角不等式修剪、多辨析率检索方法、过滤精炼方案等.最后讨论并分析了时序的近似相似搜索技术.上述所有技术通过对比,其正面和反面都被深入分析.最后指出了存在的问题和未来的研究热点和方向.Time series similarity search is regarded as one of the most promising technologies in the future. However, time series data is a typical high dimensional and massive data. Developing efficient algorithms is very important for fast time series similarity queries. The paper provides an overview of research progress, and gives main research content and directions in the field. Then, some paradigms in time series applications are introduced and the performance of some typical algorithms is analyzed quantitatively. Next, this paper surveys the underlying technologies of efficient similarity queries on time series, such as bounding filtering, triangle inequality pruning, multi-resolution approach, and fitter-refine scheme, etc. Furthermore, the main methods for approximate similarity search are summarized and analyzed. All above-mentioned technologies, the pros and cons of the techniques are discussed by comparison. Finally, some possible research hotspot and directions in the future are given.

关 键 词：时间序列 相似搜索 高效搜索方法 子时间序列 

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