Online event-driven subsequence matching over financial data streams

ABSTRACT

Subsequence similarity matching in time series databases is an important research area for many applications. This paper presents a new approximate approach for automatic online subsequence similarity matching over massive data streams. With a simultaneous on-line segmentation and pruning algorithm over the incoming stream, the resulting piecewise linear representation of the data stream features high sensitivity and accuracy. The similarity definition is based on a permutation followed by a metric distance function, which provides the similarity search with flexibility, sensitivity and scalability. Also, the metric-based indexing methods can be applied for speed-up. To reduce the system burden, the event-driven similarity search is performed only when there is a potential event. The query sequence is the most recent subsequence of piecewise data representation of the incoming stream which is automatically generated by the system. The retrieved results can be analyzed in different ways according to the requirements of specific applications. This paper discusses an application for future data movement prediction based on statistical information. Experiments on real stock data are performed. The correctness of trend predictions is used to evaluate the performance of subsequence similarity matching.

REFERENCES

• 1: C. C. Aggarwal, J. Han, J. Wang, and P. S. Yu. A Framework for Clustering Evolving Data Streams. VLDB, pages 81--92, 2003.
• 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: Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603884]
• 4: Daniel Barbará , Ping Chen, Using the fractal dimension to cluster datasets, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.260-264, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347145]
• 5: 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
• 6: J. A. Bollinger. Bollinger on Bollinger Bands. McGraw-Hill, first edition, 2001.
• 7: Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
• 8: K.-P. Chan and A.-C. Fu. Efficient Time Series Matching by Wavelets. ICDE, pages 126--133, 1999.
• 9: Tzi-cker Chiueh, Content-Based Image Indexing, Proceedings of the 20th International Conference on Very Large Data Bases, p.582-593, September 12-15, 1994
• 10: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 11: 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
• 12: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 13: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, ACM SIGMOD Record, v.23 n.2, p.419-429, June 1994
• 14: E. Fink and K. B. Pratt. Indexing of compressed time series.
• 15: A. J. Frost and R. R. Prechter. Elliott Wave Principle. New Classics Library, first edition, 1998.
• 16: Gabriel Pui Cheong Fung , Jeffrey Xu Yu , Wai Lam, News Sensitive Stock Trend Prediction, Proceedings of the 6th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, p.481-493, May 06-08, 2002
• 17: Like Gao , X. Sean Wang, Continually evaluating similarity-based pattern queries on a streaming time series, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564734]
• 18: Like Gao , Zhengrong Yao , X. Sean Wang, Evaluating continuous nearest neighbor queries for streaming time series via pre-fetching, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584872]
• 19: Johannes Gehrke , Flip Korn , Divesh Srivastava, On computing correlated aggregates over continual data streams, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.13-24, May 21-24, 2001, Santa Barbara, California, United States
• 20: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
• 21: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 22: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 23: T. Hellstrm and K. Holmstrm. "Predicting the Stock Market". 1998.
• 24: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 25: E. J. Keogh, K. Chakrabarti, M. J. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and Information Systems, 3(3):263--286, 2001.
• 26: Eamonn J. Keogh , Selina Chu , David Hart , Michael J. Pazzani, An Online Algorithm for Segmenting Time Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.289-296, November 29-December 02, 2001
• 27: D. Komo, C. Chang, and H. Ko. "Neural Network Technology for Stock Market Index Prediction". ISSIPNN, pages 543--546, 1994.
• 28: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 29: X. Liu and H. Ferhatosmanoglu. Efficient k-NN Search on Streaming Data Series. In SSTD, pages 83--101, 2003.
• 30: Yang-Sae Moon , Kyu-Young Whang , Wook-Shin Han, General match: a subsequence matching method in time-series databases based on generalized windows, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564735]
• 31: L. O'Callaghan, A. Meyerson, R. Motwani, N. Mishra, and S. Guha. Streaming-Data Algorithms for High-Quality Clustering. ICDE, pages 685--, 2002.
• 32: 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]
• 33: 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
• 34: J. Uhlmann. Satifying General Proximity Similarity Queries with Metric Trees. IPL, 4:175--179, 1991.
• 35: 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
• 36: Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
• 37: Cui Yu , Beng Chin Ooi , Kian-Lee Tan , H. V. Jagadish, Indexing the Distance: An Efficient Method to KNN Processing, Proceedings of the 27th International Conference on Very Large Data Bases, p.421-430, September 11-14, 2001
• 38: Y. Zhu and D. Shasha. StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time. VLDB, pages 358--369, 2002.