Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]


Journal of Information Science and Engineering, Vol.19 No.4, pp.697-711 (July 2003)

Dimensionality Reduction for Indexing Time Series Based on the Minimum Distance*

Sangjun Lee, Dongseop Kwon and Sukho Lee
School of Electrical Engineering and Computer Science
Seoul National University
Seoul 151-742, Korea

We address the problem of efficient similarity search based on the minimum distance in large time series databases. To support minimum distance queries, most of previous work has to take the preprocessing step of vertical shifting. However, the vertical shifting has an additional overhead in building index. In this paper, we propose a novel dimensionality reduction technique for indexing time series based on the minimum distance. We call our approach the SSV-indexing (Segmented Sum of Variation Indexing). The proposed method can match time series of similar shape without vertical shifting and guarantees no false dismissals. Several experiments are performed on real data (stock price movement) to measure the performance of the SSV-indexing.

Keywords: database, similarity search, time series, minimum distance, autocorrelation

Full Text () Retrieve PDF document (200307_10.pdf)

Received October 22, 2001; revised April 30 & August 8, 2002; accepted October 1, 2002.
Communicated by Arbee L. P. Chen.
*This work was supported in part by BK 21 prject and ITRC program.