大规模时间序列数据库降维及相似搜索  

Dimensionality Reduction and Similarity Search in Large Time Series Databases

作　　者：李爱国[1] 覃征[2] 

机构地区：[1]西安科技大学计算机科学与技术系,西安710054 [2]西安交通大学计算机科学与技术系

出　　处：《计算机学报》2005年第9期1467-1475,共9页Chinese Journal of Computers

基　　金：陕西省科学技术发展计划"十五"攻关项目基金(2000K08G12)资助

摘　　要：提出一种基于分段多项式表示(PPR)的时间序列数据库相似查询的系统化方法.PPR是一类基于线性多项式回归的正交变换.用PPR变换索引时间序列数据在理论上具备非漏报性质.文中分析了PPR的计算复杂性以及查询阈值的下界,并提出了一种衡量时间序列相似查询算法之查询效率的定量指标.与基于离散傅立叶变换(DFT)和离散小波变换(DWT)的时间序列相似查询算法所作的对比实验表明,所提算法可以用低的索引结构维数获得高的查询效率.The problem of similarity search in time series databases has attracted much research interest in the database and data mining communities in the last decade. A systemic method of indexing and similarity searching in time series databases based on Piecewise Polynomial Representation （PPR） is proposed in this paper. The idea is to map each sub-sequence into a small set of multidimensional rectangles in feature space that is spanned by base of linear polynomial. PPR is a linear polynomial representation, and PAA （Piecewise Aggregate Approximation）, an well known time series compression technique, is a special case of PPR. PPR is used as an efficient dimensionality reduction technique to permit similarity search over large time series databases without false dismissals. Computational complexity of PPR is O（n）. The lower boundaries of search threshold are estimated, and a detailed performance anlysis of proposed method is presented. The experimental results demonstrate that performances of proposed method are superior to that of DFT （Discrete Fourier Transform） and DWT （Discrete Wavelet Transform） based index techniques.

关 键 词：数据库 时间序列 相似搜索 数据挖掘 查询 

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