基于DCT的时序数据相似性搜索

Similarity search over time series data using DCT

数据的高维度是造成时序数据相似性搜索困难的主要原因。最有效的解决方法是对时序数据进行维归约,然后对压缩后的数据建立空间索引。目前维归约的方法主要是离散傅立叶变换(DFT)和离散小波变换(DWT)。提出了一种新的方法,利用离散余弦变换(DCT)进行维归约,并在此基础上给出了对时序数据进行范围查询和近邻查询的相似性搜索方法。与基于DFT、DWT的搜索方法相比,该方法在理论分析和实验结果上都显示出较高的效率。

High dimensionality is the main difficulty of similarity search over time-series data. The most promising solution involves performing dimensionality reduction on the data, then indexing the reduced data with a spatial method. Recently, two methods of dimensionality reductions have been proposed, DIrT and DWT. In this paper we proposed a new method, dimensionality reduction with DCT, and further provided the method of similarity search about range query and nearest neighbor query. Compared with those methods based on DFT and DWT, it is more efficient in theory and experiment.