We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Similarity search for numerous patterns over multiple time series streams under dynamic time warping which supports data normalization.
- Authors
Giao, Bui; Anh, Duong
- Abstract
A huge challenge in nowadays' data mining is similarity search in streaming time series under Dynamic Time Warping (DTW). In the similarity search, data normalization is a must to obtain accurate results. However, data normalization on the fly and the DTW calculation cost a great deal of computational time and memory space. In the paper, we present two methods, SUCR-DTW and ESUCR-DTW, which conduct similarity search for numerous prespecified patterns over multiple time-series streams under DTW supporting data normalization. These two methods utilize a combination of techniques to mitigate the aforementioned costs. The efficient methods inherit the cascading lower bounds introduced in UCR-DTW, a state-of-the-art method of similarity search in the static time series, to admissibly prune off unpromising subsequences. To be adaptive in the streaming setting, SUCR-DTW performs incremental updates on the envelopes of new-coming time-series subsequences and incremental data normalization on time-series data. However, like UCR-DTW, SUCR-DTW retrieves only similar subsequences that have the same length as the patterns. ESUCR-DTW, an extension of SUCR-DTW, can find similar subsequences whose lengths are different from those of the patterns. Furthermore, our proposed methods exploit multi-threading to have a fast response to high-speed time-series streams. The experimental results show that SUCR-DTW obtains the same precision as UCR-DTW and has lower wall clock time. Besides, the experimental results of SUCR-DTW and ESUCR-DTW reveal that the extended method has higher accuracy in spite of longer wall clock time. Also, the paper evaluates the influence of incremental z-score normalization and incremental min-max normalization on the obtained results.
- Subjects
TIME series analysis; NORMALIZED measures; DATA mining; THREADS (Computer programs); SIMILARITY (Geometry)
- Publication
Vietnam Journal of Computer Science (Springer Nature), 2016, Vol 3, Issue 3, p181
- ISSN
2196-8888
- Publication type
Article
- DOI
10.1007/s40595-016-0062-4