Research at Sofia University >
S3T 2011 >
Please use this identifier to cite or link to this item:
|Title: ||The Influence of Global Constraints on DTW and LCS Similarity Measures for Time-Series Databases|
|Authors: ||Kurbalija, Vladimir|
|Issue Date: ||2011|
|Publisher: ||Springer-Verlag Berlin Heidelberg 2011|
|Citation: ||Kurbalija, Vladimir, Radovanovic, Milos, Geler, Zoltan, Ivanovic, Mirjana (2011), The Influence of Global Constraints on DTW and LCS Similarity Measures for Time-Series Databases, Advances in Intelligent and Soft Computing, 2011, Volume 101, Third International Conference on Software, Services and Semantic Technologies S3T 2011, September 1-3, 2011, Bourgas, Bulgaria, ISBN 978-3-642-23162-9, pp. 67-74|
|Abstract: ||Analysis of time series represents an important tool in many application areas. A vital component in many types of time-series analysis 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. In this paper, we investigate two representative time-series distance/similarity measures based on dynamic programming, Dynamic Time Warping (DTW) and Longest Common Subsequence (LCS), and the effects of global constraints on them. Through extensive experiments on a large number of time-series data sets, we demonstrate how global constrains can significantly reduce the computation time of DTW and LCS. We also show that, if the constraint parameter is tight enough (less than 10–15% of time-series length), the constrained measure becomes significantly different from its unconstrained counterpart, in the sense of producing qualitatively different 1-nearest neighbour graphs. This observation highlights the need for careful tuning of constraint parameters in order to achieve a good trade-off between speed and accuracy.|
|Appears in Collections:||S3T 2011|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.