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}
}
BibTeX
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 ...
BibTeX
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 BibTeX
,
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) BibTeX
- [2]
- Rakesh Agrawal, Christos Faloutsos, Arun N. Swami:
Efficient Similarity Search In Sequence Databases.
FODO 1993: 69-84 BibTeX
- [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 BibTeX
- [4]
- Rakesh Agrawal, Tomasz Imielinski, Arun N. Swami:
Mining Association Rules between Sets of Items in Large Databases.
SIGMOD Conference 1993: 207-216 BibTeX
- [5]
- Khaled K. Al-Taha, Richard T. Snodgrass, Michael D. Soo:
Bibliography on Spatiotemporal Databases.
SIGMOD Record 22(1): 59-67(1993) BibTeX
- [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) BibTeX
- [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 BibTeX
- [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 BibTeX
- [10]
- ...
- [11]
- ...
- [12]
- ...
- [13]
- Christos Faloutsos:
Access Methods for Text.
ACM Comput. Surv. 17(1): 49-74(1985) BibTeX
- [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) BibTeX
- [15]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57 BibTeX
- [16]
- ...
- [17]
- H. V. Jagadish:
Spatial Search with Polyhedra.
ICDE 1990: 311-319 BibTeX
- [18]
- H. V. Jagadish:
A Retrieval Technique for Similar Shapes.
SIGMOD Conference 1991: 208-217 BibTeX
- [19]
- Ibrahim Kamel, Christos Faloutsos:
On Packing R-trees.
CIKM 1993: 490-499 BibTeX
- [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 BibTeX
- [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) BibTeX
- [23]
- ...
- [24]
- Jack A. Orenstein:
Spatial Query Processing in an Object-Oriented Database System.
SIGMOD Conference 1986: 326-336 BibTeX
- [25]
- ...
- [26]
- Hanan Samet:
The Design and Analysis of Spatial Data Structures.
Addison-Wesley 1990
BibTeX
- [27]
- ...
- [28]
- Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518 BibTeX
- [29]
- Robert B. Stam, Richard T. Snodgrass:
A Bibliography on Temporal Databases.
IEEE Data Eng. Bull. 11(4): 53-61(1988) BibTeX
- [30]
- ...
- [31]
- Gregory K. Wallace:
The JPEG Still Picture Compression Standard.
Commun. ACM 34(4): 30-44(1991) BibTeX
Referenced by
- Christos Faloutsos, Bernhard Seeger, Agma J. M. Traina, Caetano Traina Jr.:
Spatial Join Selectivity Using Power Laws.
SIGMOD Conference 2000: 177-188
- Christian Böhm, Hans-Peter Kriegel:
Dynamically Optimizing High-Dimensional Index Structures.
EDBT 2000: 36-50
- Tolga Bozkaya, Z. Meral Özsoyoglu:
Indexing Large Metric Spaces for Similarity Search Queries.
ACM Trans. Database Syst. 24(3): 361-404(1999)
- Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang:
High Level Indexing of User-Defined Types.
VLDB 1999: 554-564
- Kelvin Kam Wing Chu, Man Hon Wong:
Fast Time-Series Searching with Scaling and Shifting.
PODS 1999: 237-248
- Davood Rafiei:
On Similarity-Based Queries for Time Series Data.
ICDE 1999: 410-417
- Guido Proietti, Christos Faloutsos:
I/O Complexity for Range Queries on Region Data Stored Using an R-tree.
ICDE 1999: 628-635
- Kin-pong Chan, Ada Wai-Chee Fu:
Efficient Time Series Matching by Wavelets.
ICDE 1999: 126-133
- Michael Ortega, Yong Rui, Kaushik Chakrabarti, Kriengkrai Porkaew, Sharad Mehrotra, Thomas S. Huang:
Supporting Ranked Boolean Similarity Queries in MARS.
IEEE Trans. Knowl. Data Eng. 10(6): 905-925(1998)
- Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas:
Fast and Effective Retrieval of Medical Tumor Shapes.
IEEE Trans. Knowl. Data Eng. 10(6): 889-904(1998)
- Mihael Ankerst, Hans-Peter Kriegel, Thomas Seidl:
A Multistep Approach for Shape Similarity Search in Image Databases.
IEEE Trans. Knowl. Data Eng. 10(6): 996-1004(1998)
- Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl:
Improving Adaptable Similarity Query Processing by Using Approximations.
VLDB 1998: 206-217
- Thomas Seidl, Hans-Peter Kriegel:
Optimal Multi-Step k-Nearest Neighbor Search.
SIGMOD Conference 1998: 154-165
- Apostolos Papadopoulos, Yannis Manolopoulos:
Similarity Query Processing Using Disk Arrays.
SIGMOD Conference 1998: 225-236
- Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh:
Dimensionality Reduction for Similarity Searching in Dynamic Databases.
SIGMOD Conference 1998: 166-176
- Byoung-Kee Yi, H. V. Jagadish, Christos Faloutsos:
Efficient Retrieval of Similar Time Sequences Under Time Warping.
ICDE 1998: 201-208
- Nick Koudas, Kenneth C. Sevcik:
High Dimensional Similarity Joins: Algorithms and Performance Evaluation.
ICDE 1998: 466-475
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
Using Extended Feature Objects for Partial Similarity Retrieval.
VLDB J. 6(4): 333-348(1997)
- John C. Shafer, Rakesh Agrawal:
Parallel Algorithms for High-dimensional Similarity Joins for Data Mining Applications.
VLDB 1997: 176-185
- Thomas Seidl, Hans-Peter Kriegel:
Efficient User-Adaptable Similarity Search in Large Multimedia Databases.
VLDB 1997: 506-515
- Paolo Ciaccia, Marco Patella, Pavel Zezula:
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces.
VLDB 1997: 426-435
- Davood Rafiei, Alberto O. Mendelzon:
Similarity-Based Queries for Time Series Data.
SIGMOD Conference 1997: 13-25
- Tolga Bozkaya, Z. Meral Özsoyoglu:
Distance-Based Indexing for High-Dimensional Metric Spaces.
SIGMOD Conference 1997: 357-368
- A. Prasad Sistla, Clement T. Yu, R. Venkatasubrahmanian:
Similarity Based Retrieval of Videos.
ICDE 1997: 181-190
- Ming-Syan Chen, Jiawei Han, Philip S. Yu:
Data Mining: An Overview from a Database Perspective.
IEEE Trans. Knowl. Data Eng. 8(6): 866-883(1996)
- Rosa Meo, Giuseppe Psaila, Stefano Ceri:
A New SQL-like Operator for Mining Association Rules.
VLDB 1996: 122-133
- Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas:
Fast Nearest Neighbor Search in Medical Image Databases.
VLDB 1996: 215-226
- Christos Faloutsos, Volker Gaede:
Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension.
VLDB 1996: 40-50
- Nasser Yazdani, Z. Meral Özsoyoglu:
Sequence Matching of Images.
SSDBM 1996: 53-62
- David A. White, Ramesh Jain:
Similarity Indexing with the SS-tree.
ICDE 1996: 516-523
- Hagit Shatkay, Stanley B. Zdonik:
Approximate Queries and Representations for Large Data Sequences.
ICDE 1996: 536-545
- Chung-Sheng Li, Philip S. Yu, Vittorio Castelli:
HierarchyScan: A Hierarchical Similarity Search Algorithm for Databases of Long Sequences.
ICDE 1996: 546-553
- Gultekin Özsoyoglu, Richard T. Snodgrass:
Temporal and Real-Time Databases: A Survey.
IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
- Christos Faloutsos:
Fast Searching by Content in Multimedia Databases.
IEEE Data Eng. Bull. 18(4): 31-40(1995)
- Alberto Belussi, Christos Faloutsos:
Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension.
VLDB 1995: 299-310
- Rakesh Agrawal, King-Ip Lin, Harpreet S. Sawhney, Kyuseok Shim:
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases.
VLDB 1995: 490-501
- H. V. Jagadish, Alberto O. Mendelzon, Tova Milo:
Similarity-Based Queries.
PODS 1995: 36-45
- Bharathi Subramanian, Theodore W. Leung, Scott L. Vandenberg, Stanley B. Zdonik:
The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases.
ICDE 1995: 80-89
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:22 2009