Fast Subsequence Matching in Time-Series Databases
Fast Subsequence Matching in Time-Series Databases
Files
Publication or External Link
Date
1998-10-15
Authors
Faloutsos, Christos
Ranganathan, M.
Manolopoulos, Yannis
Advisor
Citation
DRUM DOI
Abstract
We present an efficient indexing method to locate 1-dimensional
subsequences within a collection of sequences, such that the
subsequences match a given (query) pattern within a specified tolerance.
The idea is to map each data sequence into a small set of
multidimensional rectangles in feature space.
Then, these rectangles can be readily indexed using traditional
spatial access methods, like the R*-tree \cite{Beckmann90R}.
In more detail, we use a sliding window over the data sequence
and extract its features; the result is a trail in feature space.
We propose an efficient and effective algorithm to divide such trails
into sub-trails, which are subsequently represented by their
Minimum Bounding Rectangles (MBRs). We also examine queries of
varying lengths, and we show how to handle each case efficiently.
We implemented our method and carried out
experiments on synthetic and real data (stock price movements).
We compared the method to sequential scanning,
which is the only obvious competitor. The results were excellent:
our method accelerated the search time from 3 times up to 100 times.
Appeared in ACM SIGMOD 1994, pp 419-429. Given "Best Paper award"
(Also cross-referenced as UMIACS-TR-93-131)