Adaptive burst detection in a stream engine

ABSTRACT

Detecting bursts in data streams is an important and challenging task. Due to the complexity of this task, usually burst detection cannot be formulated using standard query operators. Therefore, we show how to integrate burst detection for stationary as well as non-stationary data into query formulation and processing, from the language level to the operator level. Afterwards, we present fundamentals of threshold-based burst detection. We focus on the applicability of time series forecasting techniques in order to dynamically identify suitable thresholds for stream data containing arbitrary trends and periods. The proposed approach is evaluated with respect to quality and performance on synthetic and real-world sensor data using a full-fledged DSMS.

REFERENCES

• 1: Arasu, A., Babu, S., and Widom, J. The CQL Continuous Query Language: Semantic Foundations and Query Execution. Tech. rep., University of Stanford, 2003.
• 2: Chatfield, C., and Yar, M. Holt-Winters Forecasting: Some Practical Issues. The Statistician, Special Issue: Statistical Forecasting and Decision-Making 37, 2 (1988), 129--140.
• 3: Ergün, F., Muthukrishnan, S., and Sahinalp, S. C. Sublinear methods for detecting periodic trends in data streams. In LATIN (2004).
• 4: Hinneburg, A., Habich, D., and Karnstedt, M. Analyzing Data Streams by Online DFT. In IWKDDS-2006 (2006), pp. 67--76.
• 5: Eamonn Keogh , Stefano Lonardi , Bill 'Yuan-chi' Chiu, Finding surprising patterns in a time series database in linear time and space, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775128]
• 6: Jon Kleinberg, Bursty and Hierarchical Structure in Streams, Data Mining and Knowledge Discovery, v.7 n.4, p.373-397, October 2003 [doi>10.1023/A:1024940629314]
• 7: Spiros Papadimitriou , Anthony Brockwell , Christos Faloutsos, Adaptive, hands-off stream mining, Proceedings of the 29th international conference on Very large data bases, p.560-571, September 09-12, 2003, Berlin, Germany
• 8: Cyrus Shahabi , Xiaoming Tian , Wugang Zhao, TSA-Tree: A Wavelet-Based Approach to Improve the Efficiency of Multi-Level Surprise and Trend Queries on Time-Series Data, Proceedings of the 12th International Conference on Scientific and Statistical Database Management, p.55, July 26-28, 2000 [doi>10.1109/SSDM.2000.869778]
• 9: Dennis Shasha , Yunyue Zhu, High Performance Discovery In Time Series: Techniques And Case Studies (Monographs in Computer Science), SpringerVerlag, 2004
• 10: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 11: Wang, M., Madhyastha, T. M., Chan, N. H., Papadimitriou, S., and Faloutsos, C. Data mining meets performance evaluation: Fast algorithms for modeling bursty traffic. In ICDE (2002).
• 12: Kenji Yamanishi , Jun-ichi Takeuchi, A unifying framework for detecting outliers and change points from non-stationary time series data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775148]
• 13: Xin Zhang , Dennis Shasha, Better Burst Detection, Proceedings of the 22nd International Conference on Data Engineering, p.146, April 03-07, 2006 [doi>10.1109/ICDE.2006.30]
• 14: Yunyue Zhu , Dennis Shasha, Efficient elastic burst detection in data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956789]