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

Dimensionality Reduction and Similarity Search in Large Time Series Databases

提出一种基于分段多项式表示(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.