Stream Monitoring under the Time Warping Distance
Published 1 April 2007
Yasushi Sakurai, Christos Faloutsos, Masashi Yamamuro
Citations226
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A theoretical analysis is provided and it is proved that SPRING does not sacrifice accuracy, while it requires constant space and time per time-tick, and that it can offer dramatic improvements in speed over the naive implementation.
Abstract
The goal of this paper is to monitor numerical streams, and to find subsequences that are similar to a given query sequence, under the DTW (dynamic time warping) distance. Applications include word spotting, sensor pattern matching, and monitoring of bio-medical signals (e.g., EKG, ECG), and monitoring of environmental (seismic and volcanic) signals. DTW is a very popular distance measure, permitting accelerations and decelerations, and it has been studied for finite, stored sequence sets. However, in many applications such as network analysis and sensor monitoring, massive amounts of data arrive continuously and it is infeasible to save all the historical data. We propose SPRING, a novel algorithm that can solve the problem. We provide a theoretical analysis and prove that SPRING does not sacrifice accuracy, while it requires constant space and time per time-tick. These are dramatic improvements over the naive method. Our experiments on real and realistic data illustrate that SPRING does indeed detect the qualifying subsequences correctly and that it can offer dramatic improvements in speed over the naive implementation.
Keywords
Computer Science
Fundamentals of speech recognition
7,687 Citations1993Lawrence R. Rabiner, Biing‐Hwang Juang
This book presents a meta-modelling framework for speech recognition that automates the very labor-intensive and therefore time-heavy and therefore expensive and expensive process of manually modeling speech.
Knowledge and Information SystemsExact indexing of dynamic time warping
1,949 Citations2004Eamonn Keogh, Chotirat Ann Ratanamahatana
This work introduces a novel technique for the exact indexing of Dynamic time warping and proves its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken.
IEEE Transactions on Knowledge and Data EngineeringClustering data streams: theory and practice
896 Citations2003Suvajyoti Guha, Adam Meyerson +3 more
This work describes a streaming algorithm that effectively clusters large data streams and provides empirical evidence of the algorithm's performance on synthetic and real data streams.
Efficient retrieval of similar time sequences under time warping
713 Citations2002Byoung-Kee Yi, H. V. Jagadish +1 more
This work proposes a modification of the so called "FastMap", to map sequences into points, with little compromise of "recall" (typically zero), and a fast linear test, to help to discard quickly many of the false alarms that FastMap will typically introduce.
Elsevier eBooksStatStream
655 Citations2002Yunyue Zhu, Dennis Shasha
This chapter solves the problem of maintaining multistream and time-delayed statistics in a scalable way that gives a guaranteed response time with high accuracy and Experiments conducted using synthetic and real data show that StatStream detects correlations efficiently and precisely.
Exact indexing of dynamic time warping
601 Citations2002Eamonn Keogh
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
379 Citations2001Anna C. Gilbert, Yannis Kotidis +2 more
This work presents general “sketch” based methods for capturing various linear projections of the data and use them to provide pointwise and rangesum estimation of data streams.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Streaming Pattern Discovery in Multiple Time-Series
353 Citations2018Spiros Papadimitriou, Jimeng Sun +1 more
SPIRIT can incrementally capture correlations and discover trends, efficiently and effectively, and be used to immediately spot potential anomalies, to do efficient forecasting and to dramatically simplify further data processing.
An index-based approach for similarity search supporting time warping in large sequence databases
309 Citations2002Sang‐Wook Kim, Sanghyun Park +1 more
A new distance function D/sub tw-lb/ that consistently underestimates the time warping distance and also satisfies the triangular inequality is devised and achieves significant speedup up to 43 times with real-world S&P 500 stock data and up to 720 times with very large synthetic data.
Warping indexes with envelope transforms for query by humming
247 Citations2003Yunyue Zhu, Dennis Shasha
This work treats music as a time series and exploit and improve well-developed techniques from time series databases to index the music for fast similarity queries and improves on existing DTW indexes technique by introducing the concept of envelope transforms, which gives a general guideline for extending existing dimensionality reduction methods toDTW indexes.
FTW
230 Citations2005Yasushi Sakurai, Masatoshi Yoshikawa +1 more
Experiments on real and synthetic sequence data sets reveals that FTW is significantly faster than the best existing method, up to 222 times, and efficiently prunes a significant number of the search cost.
BRAID
167 Citations2005Yasushi Sakurai, Spiros Papadimitriou +1 more
BRAID can handle data streams of semi-infinite length, incrementally, quickly, and with small resource consumption, and can estimate lag correlations with little, and often with no error at all.
ACM SIGKDD Explorations NewsletterMining data streams under block evolution
130 Citations2002Venkatesh Ganti, Johannes Gehrke +1 more
A generic algorithm for model maintenance that takes any traditional incremental data mining model maintenance algorithm and transforms it into an algorithm that allows restrictions on a temporal subset of the database and a framework for change detection that quantifies the difference between two datasets in terms of the data mining models they induce.
Elsevier eBooksAdaptive, Hands-Off Stream Mining
123 Citations2003Spiros Papadimitriou, Anthony Brockwell +1 more
AWSOM (Arbitrary Window Stream mOdeling Method), which allows sensors in remote or hostile environments to efficiently and effectively discover interesting patterns and trends, is proposed, which is the first method that has all the above characteristics.
Hierarchical filtering method for content-based music retrieval via acoustic input
81 Citations2001Jyh‐Shing Roger Jang, Hong-Ru Lee
An implementation of a content-based music retrieval system that can take a user's acoustic input via a microphone and then retrieve the intended song from a database containing over 3000 candidate songs, demonstrates the feasibility of real-time music retrieval with a high success rate.
Warping indexes with envelope transforms for query by humming
80 Citations2003Yunyue Zhu, Dennis Shasha
EosForensic seismology and the sinking of the Kursk
44 Citations2001Keith D. Koper, Terry C. Wallace +2 more
Efficient subsequence matching for sequences databases under time warping
33 Citations2003Tik-Shun Wong, Man Hon Wong
This paper presents a method that supports dynamic time warping for subsequence matching within a collection of sequences and takes full advantage of the "sliding window" approach and can handle queries of arbitrary length.
Automatic modeling of a 3D city map from real-world video
26 Citations1999Hiroshi Kawasaki, Tomoyuki Yatabe +2 more
The proposed method is an automatic organization method focusing on video objects to describe video data in an efficient way by collating the real-world video data with map information using DP matching, to demonstrate the reliability of this method.
Memory-Based Forecasting for Weather Image Patterns
10 Citations2000Kazuhiro Otsuka, Tsutomu Horikoshi +2 more
EosReply [to “Comment on ‘Forensic seismology and the sinking of the Kursk’”]
2 Citations2001Keith D. Koper, Terry C. Wallace +2 more