Fast subsequence matching in time-series databases

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 sequences 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 [9]. 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.

REFERENCES

• 1: R. Agrawal , T. Imielinski , A. Swami, Database Mining: A Performance Perspective, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.914-925, December 1993 [doi>10.1109/69.250074]
• 2: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 3: Rakesh Agrawal , Sakti P. Ghosh , Tomasz Imielinski , Balakrishna R. Iyer , Arun N. Swami, An Interval Classifier for Database Mining Applications, Proceedings of the 18th International Conference on Very Large Data Bases, p.560-573, August 23-27, 1992
• 4: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 5: Khaled K. Al-Taha , Richard Thomas Snodgrass , Michael D. Soo, Bibliography on spatiotemporal databases, ACM SIGMOD Record, v.22 n.1, p.59-67, March 1993 [doi>10.1145/156883.156892]
• 6: S.F. Altschul, W. Gish, W. Miller, E.W. Myers, and D.J. Lipman. A basic local alignment search tool. Journal of Molecular Biology, 1990.
• 7: Manish Arya. William Cody. Christos Faloutsos. Joel Richardson, and Arthur Toga. Qbism: a prototype 3-d medical image database system. IEEE Data Engineering Bulletin, 16(1):38-42, March 1993.
• 8: Manish Arya , William F. Cody , Christos Faloutsos , Joel Richardson , Arthur Toya, QBISM: Extending a DBMS to Support 3D Medical Images, Proceedings of the Tenth International Conference on Data Engineering, p.314-325, February 14-18, 1994
• 9: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 10: Christopher Chatfield. The Analysis of Time Series: an Introduction. Chapman and Hall, London & New York, 1984. Third Edition.
• 11: Mathematical Committeeon Physical and NSF Engineering Sciences. Grand Challenges: lIigh Performance Computing and Communications. National Science Foundation, 1992. The FY 1992 U.S. Research and Development Program.
• 12: Robert D. Edwards and John Magee. Technical Analysis of Stock Trends. John Magee, Springfield, Massachusetts, 1966. 5th Edition, second printing.
• 13: Chris Faloutsos, Access methods for text, ACM Computing Surveys (CSUR), v.17 n.1, p.49-74, March 1985 [doi>10.1145/4078.4080]
• 14: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 15: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 16: Richard Wesley Hamming. Digital Filters. Prentice-Hall Signal Processing Series, Englewood Cliffs, N.J., 1977.
• 17: H. V. Jagadish, Spatial Search with Polyhedra, Proceedings of the Sixth International Conference on Data Engineering, p.311-319, February 05-09, 1990
• 18: H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States
• 19: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 20: B. Mandelbrot. Fraetal Geometry of Nature. W.H. Freeman, New York, 1977.
• 21: Wayne Niblaek, Ron Barber, Will Equitz, Myron Flickner, Eduardo Glasman, Dragutin Petkovie, Peter Yanker, Christos Faloutsos, and Gabriel Taubin. The qbie project: Querying images by content using color, texture and shape. SPIE 1993 Intl. Symposium on Electronic Imaging: Science and Technology, Conf. 1908, Storage and Retrieval for Image and Video Databases, February 1993. Also available as IBM Research Report ILl 9203 (81511), Feb. 1, 1993, Computer Science.
• 22: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 23: Alan Victor Oppenheim and Ronald W. Schafer. Digital Signal Processing. Prentice-Hall, Englewood Cliffs, N.J., 1975.
• 24: Jack A. Orenstein, Spatial query processing in an object-oriented database system, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.326-336, May 28-30, 1986, Washington, D.C., United States
• 25: Mary Beth Ruskai, Gregory Beylkin, Ronald Coifman, Ingrid Daubeehies, Stephane Mallat, Yves Meyer, and Louise Raphael. Wavelets and Their Applications. Jones and Bartlett Publishers, Boston, MA, 1992.
• 26: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 27: Manfred Sehroeder. Fractals, Chaos, Power Laws: Minutes From an lnfinite Paradise. W.H. Freeman and Company, New York, 1991.
• 28: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 29: R. Stam and Richard Snodgrass. A bibliography on temporal databases. IEEE Bulletin on Data Engineering, 11(4), December 1988.
• 30: Dimitris Vassiliadis. The input-state space approach to the prediction of auroral geomagnetic activity from solar wind variables. Int. Workshop on Applications of Artificial Intelligence in Solar Terrestrial Physics, September 1993.
• 31: Gregory K. Wallace, The JPEG still picture compression standard, Communications of the ACM, v.34 n.4, p.30-44, April 1991 [doi>10.1145/103085.103089]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Theory, Verification