Effective Filtering for Nearest-Neighbors Queries in Large Time-Series Databases

Abstract

Time-series data are periodic recordings of time-varying information. Since the data are temporal in nature, finding a similar data sequence in time-series databases to a given query is very costly. The straight forward strategy to examine each possible occurrence by sliding a window over each database sequence will take quadratic computation cost. For large time-series databases, this approach is practically infeasible. To shorten query response time, we propose in this paper a low-cost filtering mechanism to sieve out the most similar candidates from the dissimilar ones in the database. Then, only small portions of database require the true similarity measurement to finalize the query. As a result,our preprocessing approach achieves significant savings in overall query processing. We show our filtering technique incur no false dismissals, and has greater pruning power than the other competing schemes. Empirical results indicate 57% of non-similar data can be filtered out without resorting to the expensive true similarity measurement.