2008 · 10 citations · 14 references
ComputingComputer ScienceData MiningSequence AnalysisTime Series AnalysisDynamic Time WarpingSequence MiningSequence Pattern RecognitionSequence Similarity SearchStream ProcessingStreaming AlgorithmsData Stream MiningPattern Matching AlgorithmsScalable Similarity SearchSimilarity DetectionStream MiningStreaming Data MiningStreaming MatchingTime Series Similarity Search
Data stream has attracted many researchers from various communities (network, database and data mining). There are a variety of techniques for solving the similarity matching in time series datasets. However, subsequence matching over data stream, finding those subsequences which are similar to a query sequence in a progressive and real-time fashion, is a challenging and novel problem due to the high speed, large quantity, potentially unbounded and evolving stream data. In this paper, firstly, we design a bound technique to prune the unnecessary computation as much as possible. Then, a novel algorithm is proposed which can identify all matched subsequences from data stream under the DTW (Dynamic Time Warping) distance in a “single pass”. Furthermore, our experiments on synthetic and real data show that the proposed method is at least 3 times faster than the existing algorithm: SPRING, only increasing several extra bytes.
14
Models and issues in data stream systems
Brian Babcock, Shivnath Babu, Mayur Datar et al. · 2002 · 2.5K citations
Models and issues in data stream systems
Brian Babcock, Shivnath Babu, Mayur Datar et al. · 2002 · 746 citations
Exact indexing of dynamic time warping
Eamonn Keogh · 2002 · 603 citations