Title :
Memory-efficient centroid decomposition for long time series
Author :
Khayati, Mourad ; Bohlen, M. ; Gamper, J.
Author_Institution :
Dept. of Comput. Sci., Univ. of Zurich, Zurich, Switzerland
fDate :
March 31 2014-April 4 2014
Abstract :
Real world applications that deal with time series data often rely on matrix decomposition techniques, such as the Singular Value Decomposition (SVD). The Centroid Decomposition (CD) approximates the Singular Value Decomposition, but does not scale to long time series because of the quadratic space complexity of the sign vector computation. In this paper, we propose a greedy algorithm, termed Scalable Sign Vector (SSV), to efficiently determine sign vectors for CD applications with long time series, i.e., where the number of rows (observations) is much larger than the number of columns (time series). The SSV algorithm starts with a sign vector consisting of only 1s and iteratively changes the sign of the element that maximizes the benefit. The space complexity of the SSV algorithm is linear in the length of the time series. We provide proofs for the scalability, the termination and the correctness of the SSV algorithm. Experiments with real world hydrological time series and data sets from the UCR repository validate the analytical results and show the scalability of SSV.
Keywords :
approximation theory; data handling; greedy algorithms; mathematics computing; singular value decomposition; time series; vectors; CD; SSV algorithm; SVD; UCR repository; approximation; greedy algorithm; hydrological time series; matrix decomposition techniques; memory-efficient centroid decomposition; quadratic space complexity; scalable sign vector; sign vector computation; singular value decomposition; time series data; Complexity theory; Loading; Matrix decomposition; Runtime; Singular value decomposition; Time series analysis; Vectors;
Conference_Titel :
Data Engineering (ICDE), 2014 IEEE 30th International Conference on
Conference_Location :
Chicago, IL
DOI :
10.1109/ICDE.2014.6816643