A Query Adaptive Data Structure for Efficient Indexing of Time Series Databases

Speaker: Stavros Papadopoulos

Abstract

Dimensionality reduction for efficient similarity search in time series databases has attracted a lot of research interest in the last few years. Although the proposed methods so far may differ in pruning power, reconstruction error and dataset sensitivity, they all share a common characteristic. They all transform a time series into a relatively small number of features that are indexed in a reduced space, in order to approximate the original time series and allow fast similarity search queries. However, the problem of finding the optimal number of features to be used in order to achieve optimal query times has not been addressed yet, since the increase of features results in bad index search times, whereas a small number of features may lead to many expensive false alarms. In this work we attempt to introduce a query adaptive data structure, which allows multiple dimensionalities within its structure and dynamically adjusts the dimensionality of the individual nodes/MBRs as queries arrive in time. In this way we achieve the optimal tradeoff between index search times and accuracy, a fact that results in smaller query times.