I.F. Vega-López (Mexico) and B. Moon (USA)
Time Series, Time Warping, Similarity Search.
Indexing Time Series Data is an interesting problem that has attracted much interest in the research community for the last decade. Traditional indexing methods organize the data space using different metrics. For time series, how ever, there are some cases when a metric is not suited for properly assessing the similarity between sequences. For instance, to detect similarities between sequences that are locally out of phase Dynamic Time Warping (DTW) must be used. DTW is not a metric as it does not satisfy the trian gular inequality. Therefore, traditional spatial access meth ods cannot be used without introducing false dismissals. In such cases, alternative methods for organizing and search ing time series data must be proposed. In this paper we propose the use of quantization to generate small and ho mogeneous representations of time series. We compute upper- and lower-bounds on the DTW distance to a query sequence using this quantized representation to filter-out sequences that cannot be a best match for the query. In the proposed approach, efficient search is achieved by organiz ing the quantized representation of data in a linear array that can be efficiently read from disk. The computational cost of processing the query is shadowed by the IO cost re quired to scan the file containing the linear array and it does affect the total query cost.
Important Links:
Go Back
