Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-23088-2_16
Title: Similar subsequence search in time series databases
Authors: Kashyap, S.
Lee, M.L. 
Hsu, W. 
Issue Date: 2011
Source: Kashyap, S.,Lee, M.L.,Hsu, W. (2011). Similar subsequence search in time series databases. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6860 LNCS (PART 1) : 232-246. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-23088-2_16
Abstract: Finding matching subsequences in time series data is an important problem. The classical approach to search for matching subsequences has been on the principle of exhaustive search, where all possible candidates are generated and evaluated or all the terms of the time series in a data base are examined. As a result most of the subsequence search algorithms are cubic in nature with few algorithms of quadratic nature. Some approximate algorithms have been proposed, as a result, to speed up the search for matching subsequences. In this work, we propose a fast and efficient exact subsequence search algorithm which is sub-quadratic in nature. We introduce the notion of eHaar (envelope Haar) to prune parts of the time series data which will not contain subsequences that can match the query subsequence. This pruning phase dramatically reduces the search space, thus allowing dynamic time warping based subsequence search techniques to be applied on gigabyte-size time series databases. Experiment results demonstrate that the proposed approach outperforms existing state-of-the art techniques. © 2011 Springer-Verlag Berlin Heidelberg.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40906
ISBN: 9783642230875
ISSN: 03029743
DOI: 10.1007/978-3-642-23088-2_16
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

4
checked on Dec 13, 2017

Page view(s)

57
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.