ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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.


ACM SIGMOD Anthology

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

Online Edition: ACM Digital Library

[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

  1. Christos Faloutsos, Bernhard Seeger, Agma J. M. Traina, Caetano Traina Jr.: Spatial Join Selectivity Using Power Laws. SIGMOD Conference 2000: 177-188
  2. Christian Böhm, Hans-Peter Kriegel: Dynamically Optimizing High-Dimensional Index Structures. EDBT 2000: 36-50
  3. Tolga Bozkaya, Z. Meral Özsoyoglu: Indexing Large Metric Spaces for Similarity Search Queries. ACM Trans. Database Syst. 24(3): 361-404(1999)
  4. 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
  5. Kelvin Kam Wing Chu, Man Hon Wong: Fast Time-Series Searching with Scaling and Shifting. PODS 1999: 237-248
  6. Davood Rafiei: On Similarity-Based Queries for Time Series Data. ICDE 1999: 410-417
  7. Guido Proietti, Christos Faloutsos: I/O Complexity for Range Queries on Region Data Stored Using an R-tree. ICDE 1999: 628-635
  8. Kin-pong Chan, Ada Wai-Chee Fu: Efficient Time Series Matching by Wavelets. ICDE 1999: 126-133
  9. 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)
  10. 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)
  11. 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)
  12. Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl: Improving Adaptable Similarity Query Processing by Using Approximations. VLDB 1998: 206-217
  13. Thomas Seidl, Hans-Peter Kriegel: Optimal Multi-Step k-Nearest Neighbor Search. SIGMOD Conference 1998: 154-165
  14. Apostolos Papadopoulos, Yannis Manolopoulos: Similarity Query Processing Using Disk Arrays. SIGMOD Conference 1998: 225-236
  15. Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh: Dimensionality Reduction for Similarity Searching in Dynamic Databases. SIGMOD Conference 1998: 166-176
  16. Byoung-Kee Yi, H. V. Jagadish, Christos Faloutsos: Efficient Retrieval of Similar Time Sequences Under Time Warping. ICDE 1998: 201-208
  17. Nick Koudas, Kenneth C. Sevcik: High Dimensional Similarity Joins: Algorithms and Performance Evaluation. ICDE 1998: 466-475
  18. Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: Using Extended Feature Objects for Partial Similarity Retrieval. VLDB J. 6(4): 333-348(1997)
  19. John C. Shafer, Rakesh Agrawal: Parallel Algorithms for High-dimensional Similarity Joins for Data Mining Applications. VLDB 1997: 176-185
  20. Thomas Seidl, Hans-Peter Kriegel: Efficient User-Adaptable Similarity Search in Large Multimedia Databases. VLDB 1997: 506-515
  21. Paolo Ciaccia, Marco Patella, Pavel Zezula: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. VLDB 1997: 426-435
  22. Davood Rafiei, Alberto O. Mendelzon: Similarity-Based Queries for Time Series Data. SIGMOD Conference 1997: 13-25
  23. Tolga Bozkaya, Z. Meral Özsoyoglu: Distance-Based Indexing for High-Dimensional Metric Spaces. SIGMOD Conference 1997: 357-368
  24. A. Prasad Sistla, Clement T. Yu, R. Venkatasubrahmanian: Similarity Based Retrieval of Videos. ICDE 1997: 181-190
  25. 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)
  26. Rosa Meo, Giuseppe Psaila, Stefano Ceri: A New SQL-like Operator for Mining Association Rules. VLDB 1996: 122-133
  27. Flip Korn, Nikolaos Sidiropoulos, Christos Faloutsos, Eliot Siegel, Zenon Protopapas: Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996: 215-226
  28. Christos Faloutsos, Volker Gaede: Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension. VLDB 1996: 40-50
  29. Nasser Yazdani, Z. Meral Özsoyoglu: Sequence Matching of Images. SSDBM 1996: 53-62
  30. David A. White, Ramesh Jain: Similarity Indexing with the SS-tree. ICDE 1996: 516-523
  31. Hagit Shatkay, Stanley B. Zdonik: Approximate Queries and Representations for Large Data Sequences. ICDE 1996: 536-545
  32. Chung-Sheng Li, Philip S. Yu, Vittorio Castelli: HierarchyScan: A Hierarchical Similarity Search Algorithm for Databases of Long Sequences. ICDE 1996: 546-553
  33. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  34. Christos Faloutsos: Fast Searching by Content in Multimedia Databases. IEEE Data Eng. Bull. 18(4): 31-40(1995)
  35. Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310
  36. 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
  37. H. V. Jagadish, Alberto O. Mendelzon, Tova Milo: Similarity-Based Queries. PODS 1995: 36-45
  38. 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