Fast Subsequence Matching in Time-Series Databases.
Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos:
Fast Subsequence Matching in Time-Series Databases.
SIGMOD Conference 1994: 419-429@inproceedings{DBLP:conf/sigmod/FaloutsosRM94,
author = {Christos Faloutsos and
M. Ranganathan and
Yannis Manolopoulos},
editor = {Richard T. Snodgrass and
Marianne Winslett},
title = {Fast Subsequence Matching in Time-Series Databases},
booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
publisher = {ACM Press},
year = {1994},
pages = {419-429},
ee = {http://doi.acm.org/10.1145/191839.191925, db/conf/sigmod/FaloutsosRM94.html},
crossref = {DBLP:conf/sigmod/94},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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 [Beckmann et al, SIGMOD 90].
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.
Copyright © 1994 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Richard T. Snodgrass, Marianne Winslett (Eds.):
Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994.
ACM Press 1994 
,
SIGMOD Record 23(2),
June 1994
Contents
[Abstract and Index Terms]
[Full Text in PDF Format, 987 KB]
References
- [1]
- Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami:
Database Mining: A Performance Perspective.
IEEE Trans. Knowl. Data Eng. 5(6): 914-925(1993)
- [2]
- Rakesh Agrawal, Christos Faloutsos, Arun N. Swami:
Efficient Similarity Search In Sequence Databases.
FODO 1993: 69-84
- [3]
- Rakesh Agrawal, Sakti P. Ghosh, Tomasz Imielinski, Balakrishna R. Iyer, Arun N. Swami:
An Interval Classifier for Database Mining Applications.
VLDB 1992: 560-573
- [4]
- Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami:
Mining Association Rules between Sets of Items in Large Databases.
SIGMOD Conference 1993: 207-216
- [5]
- Khaled K. Al-Taha, Richard T. Snodgrass, Michael D. Soo:
Bibliography on Spatiotemporal Databases.
SIGMOD Record 22(1): 59-67(1993)
- [6]
- ...
- [7]
- Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya:
QBISM: A Prototype 3-D Medical Image Database System.
IEEE Data Eng. Bull. 16(1): 38-42(1993)
- [8]
- Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya:
QBISM: Extending a DBMS to Support 3D Medical Images.
ICDE 1994: 314-325
- [9]
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331
- [10]
- ...
- [11]
- ...
- [12]
- ...
- [13]
- Christos Faloutsos:
Access Methods for Text.
ACM Comput. Surv. 17(1): 49-74(1985)
- [14]
- Christos Faloutsos, Ron Barber, Myron Flickner, Jim Hafner, Wayne Niblack, Dragutin Petkovic, William Equitz:
Efficient and Effective Querying by Image Content.
J. Intell. Inf. Syst. 3(3/4): 231-262(1994)
- [15]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
- [16]
- ...
- [17]
- H. V. Jagadish:
Spatial Search with Polyhedra.
ICDE 1990: 311-319
- [18]
- H. V. Jagadish:
A Retrieval Technique for Similar Shapes.
SIGMOD Conference 1991: 208-217
- [19]
- Ibrahim Kamel, Christos Faloutsos:
On Packing R-trees.
CIKM 1993: 490-499
- [20]
- ...
- [21]
- Wayne Niblack, Ron Barber, William Equitz, Myron Flickner, Eduardo H. Glasman, Dragutin Petkovic, Peter Yanker, Christos Faloutsos, Gabriel Taubin:
The QBIC Project: Querying Images by Content, Using Color, Texture, and Shape.
Storage and Retrieval for Image and Video Databases (SPIE) 1993: 173-187
- [22]
- Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik:
The Grid File: An Adaptable, Symmetric Multikey File Structure.
ACM Trans. Database Syst. 9(1): 38-71(1984)
- [23]
- ...
- [24]
- Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336
- [25]
- ...
- [26]
- Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
- [27]
- ...
- [28]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518
- [29]
- Robert B. Stam, Richard T. Snodgrass:
A Bibliography on Temporal Databases.
IEEE Data Eng. Bull. 11(4): 53-61(1988)
- [30]
- ...
- [31]
- Gregory K. Wallace:
The JPEG Still Picture Compression Standard.
Commun. ACM 34(4): 30-44(1991)
Copyright © Fri Mar 12 17:21:31 2010
by Michael Ley (ley@uni-trier.de)
