Similar Subsequence Search in Time Series Databases

Autor:	Wynne Hsu, Mong Li Lee, Shrikant Kashyap
Rok vydání:	2011
Předmět:	Dynamic time warping Database Series (mathematics) Matching (graph theory) Computer science Brute-force search Longest increasing subsequence computer.software_genre Longest common subsequence problem Search algorithm Subsequence Longest alternating subsequence computer Algorithm
Zdroj:	Lecture Notes in Computer Science ISBN: 9783642230875 DEXA (1)
DOI:	10.1007/978-3-642-23088-2_16
Popis:	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 subquadratic 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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c11e3ad14f75fd340e86bad5dbf706da https://doi.org/10.1007/978-3-642-23088-2_16 Zobrazit plný text záznamu