Shape-based retrieval of similar subsequences in time-series databases

ABSTRACT

This paper deals with the problem of shape-based retrieval in time-series databases. The shape-based retrieval is defined as the operation that searches for the (sub)sequences whose shapes are similar to that of a given query sequence. In this paper, we propose an effective and efficient approach for shape-based retrieval of subsequences. We first introduce a new similarity model for shape-based retrieval that supports various combinations of transformations such as shifting, scaling, moving average, and time warping. For efficient processing of the shape-based retrieval, we also propose the indexing and query processing methods. To verify the superiority of our approach, we perform extensive experiments with the real-world S&P 500 stock data. The results reveal that our approach successfully finds all the subsequences that have the shapes similar to that of the query sequence, and also achieves significant speedup over the sequential scan method.

REFERENCES

• 1: 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
• 2: 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, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 3: Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Zaït, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, September 11-15, 1995
• 4: Donald J. Berndt , James Clifford, Finding patterns in time series: a dynamic programming approach, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 5: C. Chatfield, The Analysis of Time-Series: An Introduction, 3rd Edition, Chapman and Hall, 1984.
• 6: Ming-Syan Chen , Jiawei Han , Philip S. Yu, Data Mining: An Overview from a Database Perspective, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.866-883, December 1996 [doi>10.1109/69.553155]
• 7: Kelvin Kam Wing Chu , Man Hon Wong, Fast time-series searching with scaling and shifting, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.237-248, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304000]
• 8: Gautam Das , Dimitrios Gunopulos , Heikki Mannila, Finding Similar Time Series, Proceedings of the First European Symposium on Principles of Data Mining and Knowledge Discovery, p.88-100, June 24-27, 1997
• 9: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: Dina Q. Goldin , Paris C. Kanellakis, On Similarity Queries for Time-Series Data: Constraint Specification and Implementation, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.137-153, September 19-22, 1995
• 11: M. Kendall, Time-Series, 2nd Edition, Charles Griffin and Company, 1979.
• 12: Sang-Wook Kim , Sanghyun Park , Wesley W. Chu, An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases, Proceedings of the 17th International Conference on Data Engineering, p.607-614, April 02-06, 2001
• 13: Lawrence Rabiner , Biing-Hwang Juang, Fundamentals of speech recognition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 14: Woong-Kee Loh , Sang-Wook Kim , Kyu-Young Whang, Index interpolation: an approach to subsequence matching supporting normalization transform in time-series databases, Proceedings of the ninth international conference on Information and knowledge management, p.480-487, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354856]
• 15: W. K. Loh, S. W. Kim, K. Y. Whang, "Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases", IEICE Trans. on Information and Systems, Vol. E84-D, No. 1, pp. 76-86, Jan. 2001.
• 16: Chihcheng Hsu, Efficient Searches for Similar Subsequences of Different Lengths in Sequence Databases, Proceedings of the 16th International Conference on Data Engineering, p.23, February 28-March 03, 2000
• 17: Sanghyun Park , Sang-Wook Kim , Wesley W. Chu, Segment-based approach for subsequence searches in sequence databases, Proceedings of the 2001 ACM symposium on Applied computing, p.248-252, March 2001, Las Vegas, Nevada, United States [doi>10.1145/372202.372334]
• 18: Sanghyun Park , Sang-Wook Kim , June-Suh Cho , Sriram Padmanabhan, Prefix-querying: an approach for effective subsequence matching under time warping in sequence databases, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502629]
• 19: Landmarks: A New Model for Similarity-Based Pattern Querying in Time Series Databases, Proceedings of the 16th International Conference on Data Engineering, p.33, February 28-March 03, 2000
• 20: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 21: Davood Rafiei , Alberto Mendelzon, Similarity-based queries for time series data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.13-25, May 11-15, 1997, Tucson, Arizona, United States
• 22: Kyuseok Shim , Ramakrishnan Srikant , Rakesh Agrawal, High-Dimensional Similarity Joins, Proceedings of the Thirteenth International Conference on Data Engineering, p.301-311, April 07-11, 1997
• 23: Graham A. Stephen, String searching algorithms, World Scientific Publishing Co., Inc., River Edge, NJ, 1994
• 24: Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos, Efficient Retrieval of Similar Time Sequences Under Time Warping, Proceedings of the Fourteenth International Conference on Data Engineering, p.201-208, February 23-27, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Size and shape

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Image databases

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Shape
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
indexing, shape-based retrieval, similarity search, time-series databases