Efficient Strategy for Out-of-Order Event Stream Processing

Yingyuan Xiao; Tao Jiang; Yan Shen; Huafeng Deng

doi:10.6180/jase.2014.17.1.09

Efficient Strategy for Out-of-Order Event Stream Processing

Computer Science and Information Engineering

Yingyuan Xiao This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Tao Jiang¹, Yan Shen¹ and Huafeng Deng²

¹Tianjin Key Laboratory of Intelligence Computing and Novel Software Technology, Key Laboratory of Computer Vision and System, Ministry of Education, Tianjin University of Technology, Tianjin-300384, P.R. China
²College of Information Technology, South China Normal University, Guangzhou-510631, P.R. China

Received: January 24, 2014
Accepted: October 7, 2013
Publication Date: March 1, 2014

Download Citation: ||https://doi.org/10.6180/jase.2014.17.1.09

ABSTRACT

Complex event processing has been widely used in many modern applications. A key aspect of complex event processing is to extract patterns from event streams to make informed decisions in real-time. However, network latencies and machine failures may cause events to arrive out-of-order at the event processing engine. To address the problem, a number of disordered event processing techniques are proposed. In this paper, we introduce latency distance and purging time to process out-of-order event streams in real-time. Further, we present a redo strategy based on playback, with which those false pattern matches produced at the early phase can be corrected by the aid of the cloud platform. We conduct extensive experiments, and the experimental results demonstrate the effectiveness of our methods.

Keywords: Out-of-Order Events, Event Stream Processing, Latency Distance, Purging Time, Redo Strategy

REFERENCES

[1] Wu, E., Diao, Y. and Rizvi, S., “High-Performance Complex Event Processing over Streams,” Proc. of 2006 SIGMOD, Chicago, U.S.A., June 2729, pp. 407418 (2006). doi: 10.1145/1142473.1142520
[2] Chen, Q., Li, Z. and Liu H., “Optimizing Complex Event Processing over RFID Data Streams,” Proc. of 2008 ICDE, Cancun, Mexico, April 712, pp. 1442 1444 (2008). doi: 10.1109/ICDE.2008.4497583
[3] Chakravarthy, S., Krishnaprasad, V., Anwar, E. and Kim, S.-K., “Composite Events for Active Databases: Semantics, Contexts and Detection,” Proc. of 1994 VLDB, Santiago, Chile, September 1215, pp. 601 617 (1994).
[4] Tucker, P. A., Maier, D., Sheard, T. and Fegaras, L., “Exploiting Punctuation Semantics in Continuous Data Streams,” IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3, pp. 555568 (2003). doi: 10.1109/TKDE.2003.1198390
[5] Srivastava, U. and Widom, J., “Flexible Time Management in Data Stream Systems,” Proc. of 2004 PODS, Paris, France, June 1315, pp. 263274 (2004). doi: 10.1145/1055558.1055596
[6] Babu, S., Srivastava, U. and Widom, J., “Exploiting k-Constraints to Reduce Memory Over-Head in Continuous Queries over Data Streams,” ACM Transitions on Database Systems, Vol. 29, No. 3, pp. 545580 (2004). doi: 10.1145/1016028.1016032
[7] Li, M., Liu, M. and Ding, L., “Event Stream Processing with Out-of-Order Data Arrival,” Proc. of 2007 ICDCSW, Toronto, Canada, June 2229, pp. 6774 (2007). doi: 10.1109/ICDCSW.2007.35
[8] Liu, M., Li, M., Golovnya, D., Rundensteiner, E. A. and Claypool, K., “Sequence Pattern Query Processing over Out-of-Order Event Streams,” Proc. of 2009 ICDE, Shanghai, China, March 29April 2, pp. 784 795 (2009). doi: 10.1109/ICDE.2009.95
[9] Wei, M. and Liu, M., “Supporting a Spectrum of Outof-Order Event Processing Technologies: From Aggressive to Conservative Methodologies,” Proc. of 2009 SIGMOD, Providence, U.S.A., June 29July 2, pp. 10311033 (2009). doi: 10.1145/1559845.1559973
[10] Zhou, C. and Meng, X., “IO3: Interval-Based Outof-Order Event Processing in Pervasive Computing,” Proc. of 2010 DASFAA, Tsukuba, Japan, April 14, pp. 261268 (2010). doi: 10.1007/978-3-642-12098- 5_20
[11] Chandramouli, B., Goldstein, J. and Maier, D., “HighPerformance Dynamic Pattern Matching over Disordered Streams,” Proc. of 2010 VLDB, Singapore, September 1317, pp. 220231 (2010).
[12] Chandramouli, B. and Goldstein, J., “Accurate Latency Estimation in a Distributed Event Processing System,” Proc. of 2011 ICDE, Hannover, Germany, April 1116, pp. 256266 (2011). doi: 10.1109/ICDE. 2011.5767926
[13] Jiang, T., Xiao, Y., Wang, X. and Li, Y., “Leveraging Communication Information among Readers for RFID Data Cleaning,” Proc. of 2011 WAIM, Wuhan, China, September 1416, pp. 201213 (2011). doi: 10.1007/ 978-3-642-23535-1_19
[14] Information on http://www.crawdad.org/meta.php? name=hope/amd.