基于小波变换的序列间距离严格估算  

The Tight Estimation Distance Using Wavelet

作　　者：刘兵[1] 汪卫[1] 施伯乐[1] 

机构地区：[1]复旦大学计算机与信息技术系,上海200433

出　　处：《计算机研究与发展》2006年第10期1732-1737,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60303008;60403018);国家"八六三"高技术研究发展计划基金项目(2002AA4Z3430)~~

摘　　要：对时间序列的相似性搜索在很多新的数据库应用中的地位变得越来越重要.使用小波变换方法缩减维度是解决高维时间序列查询的一个有效方法.给出小波变换在时间序列相似性查找中对距离上下界的一个严格估计,同时说明传统的算法只是下界的一部分.根据给出的小波变换的下界,相对于传统的算法,可以排除更多的不相似序列.根据给出的上界,可以直接判断出两条序列是否相似,进一步减少需要验证的原始序列的个数.实验结果表明,相对于传统的算法,提出的上下界可以大幅度提高过滤效果,减少查询时间.Time series similarity search is of growing importance in many applications. Wavelet transforms are used as a dimensionality reduction technique to permit efficient similarity search over high-dimensional time series data. Proposed in this paper are the tight upper and lower bounds on the estimation distance using wavelet transform, and it is shown that the traditional distance estimation is only a part of the lower bound. According to the lower bound, more dissimilar time series can be excluded than the traditional method. And according to the upper bound, whether two time series are similar can be directily judged, and the number of time series to process in the original time domain can be further reduced. The experiments show that using the upper and lower tight bounds can significantly improve the filter efficiency and reduce the running time than the traditional method.

关 键 词：时间序列 相似性搜索 小波变换 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]