Optimal Construction of Multi-Dimensional Indexes in Time-Series Databases: A Physical Database Design Approach

摘要

Similarity search in time-series databases is an operation that finds such data sequences whose changing patterns are similar to that of a query sequence. Typically, it hires the multi-dimensional index for its efficient pro-cessing. In order to alleviate the dimensionality curse, a problem in high-dimensional cases, the previous methods for similarity search apply the Discrete Fourier Trans-form(DFT) to data sequences, and take only the first two or three DFT coefficients for selecting organizing attributes of the multi-dimensional index. Other than this ad-hoc approach, there have been no research efforts on devising a systematic guideline for choosing the best organizing attributes among all the DFT coefficients. This paper first points out the problems occurred in the previous methods, and proposes a novel solution to construct the optimal multi-dimensional index. The proposed method analyzes the characteristics of a target database, and then identifies the organizing attributes having the best discrimination power. Finally, it determines the optimal number of organizing attributes by using a cost model for similarity search. We show the effectiveness of the proposed method through a series of experiments.