The influence of global constraints on similarity measures for time-series databases

Abstract

A time series consists of a series of values or events obtained over repeated measurements in time. Analysis of time series represents an important tool in many application areas, such as stock-market analysis, process and quality control, observation of natural phenomena, and medical diagnosis. A vital component in many types of time-series analyses is the choice of an appropriate distance/similarity measure. Numerous measures have been proposed to date, with the most successful ones based on dynamic programming. Being of quadratic time complexity, however, global constraints are often employed to limit the search space in the matrix during the dynamic programming procedure, in order to speed up computation. Furthermore, it has been reported that such constrained measures can also achieve better accuracy. In this paper, we investigate four representative time-series distance/similarity measures based on dynamic programming, namely Dynamic Time Warping (DTW), Longest Common Subsequence (LCS), Edit distance with Real Penalty (ERP) and Edit Distance on Real sequence (EDR), and the effects of global constraints on them when applied via the Sakoe-Chiba band. To better understand the influence of global constraints and provide deeper insight into their advantages and limitations we explore the change of the 1-nearest neighbor graph with respect to the change of the constraint size. Also, we examine how these changes reflect on the classes of the nearest neighbors of time series, and evaluate the performance of the 1-nearest neighbor classifier with respect to different distance measures and constraints. Since we determine that constraints introduce qualitative differences in all considered measures, and that different measures are affected by constraints in various ways, we expect our results to aid researchers and practitioners in selecting and tuning appropriate time-series similarity measures for their respective tasks. © 2013 Elsevier B.V. All rights reserved.