Computer Science ›› 2017, Vol. 44 ›› Issue (7): 151-160.doi: 10.11896/j.issn.1002-137X.2017.07.028

Previous Articles     Next Articles

Study of Complex Event Hierarchies Realization Based on Hierarchical Automata Model

JIN Da-wei, SHI Si, YI Cai and YANG Bing   

  • Online:2018-11-13 Published:2018-11-13

Abstract: Complex event processing technology extracts event sequences which satisfy the specific patterns (called complex events) from continuous event streams.It processes a large sum of data in real time intelligently and has attracted the attention from both academia and industry in recent years.However,the state-of-the-art researches focus on single-layer complex event detection.In fact,because business systems have different hierarchical needs of information,events in system should be processed according to their hierarchies.Single-layer complex event detection cannot afford to meet the needs of hierarchical information in different managerial hierarchies.To deal with such problem,in this work,a hierarchical complex event detection model,hierarchical automata,was defined based on the concept of event hierarchies and traditional nondeterministic finite automaton (NFA) model.Then we designed a more intuitive and effective EH-Tree structure and proposed hierarchical complex event detection (HCED) algorithm and its cost model.Finally,taking throughput and memory consumption as indexes,massive experiments were performed to compare the spatial and temporal performance of HCED algorithm based on EH-Tree and SASE algorithm based on NFA.The results testify that our HCED algorithm can perform hierarchical complex event detection effectively and efficiently,which fills in the blanks of hierarchical complex event detection and indicates that our work can be a basis for further research of complex event processing.

Key words: Complex event processing,Pattern matching,Event hierarchies,Hierarchical automata,Tree

[1] LUCKHAM D.The power of events[M].Reading:Addison-Wesley,2002.
[2] CUGOLA G,MARGARA A.Processing flows of information:from data stream to complex event processing[J].Acm Computing Surveys,2011,44(3):359-360.
[3] BALAZINSKA M,BALAKRISHNAN H,Madden S R,et al.Fault-tolerance in the Borealis distributed stream processing system[J].ACM Transactions on Database Systems (TODS),2008,33(1):3-44.
[4] O’KEEFFE D,BACON J.Reliable complex event detection for pervasive computing[C]∥Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems.ACM,2010:73-84.
[5] ZHANG H,DIAO Y,IMMERMAN N.Recognizing patterns in streams with imprecise timestamps[J].Information Systems,2013,38(8):1187-1211.
[6] ZAPPIA I,PAGANELLI F,PARLANTI D.A lightweight and extensible Complex Event Processing system for sense and respond applications[J].Expert Systems with Applications,2012,39(12):10408-10419.
[7] BOUBETA-PUGI J,ORTIZ G,MEDINA-BULO I.A model-driven approach for facilitating user-friendly design of complex event patterns[J].Expert Systems with Applications,2014,41(2):445-456.
[8] GU Y,YU G,LI C.Deadline-aware complex event processing models over distributed monitoring streams[J].Mathematical and Computer Modelling,2012,55(3):901-917.
[9] DEMERS A,GEHRKE J,HONG M,et al.Towards expressive publish/subscribe systems[M]∥Advances in Database Technology-EDBT 2006.Springer Berlin Heidelberg,2006:627-644.
[10] DEMERS A,GEHRKE J,PANDA B,et al.Cayuga:A General Purpose Event Monitoring System[C]∥CIDR.2007:412-422.
[11] HONG M,DEMERS A J,GEHRKE J E,et al.Massively multi-query join processing in publish/subscribe systems[C]∥Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data.ACM,2007:761-772.
[12] WU E,DIAO Y,RIZVI S.High-performance complex eventprocessing over streams[C]∥Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data.ACM,2006:407-418.
[13] DIAO Y,IMMERMAN N,GYLLSTROM D.Sase+:An agile language for kleene closure over event streams[J/OL].[2012-12-23].http://archive,systems,,
[14] AGRAWAL J,DIAO Y,GYLLSTROM D,et al.Efficient pattern matching over event streams[C]∥Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data.ACM,2008:147-160.
[15] GREINER T,DSTER W,POUATCHA F,et al.Business activity monitoring of norisbank taking the example of the application easycredit and the future adoption of complex event processing (CEP)[C]∥Proceedings of the 4th International Symposium on Principles and Practice of Programming in Java.ACM,2006:237-242.
[16] ADI A,BOTZER D,NECHUSHTAI G,et al.Complex event processing for financial services[C]∥Services Computing Workshops,2006(SCW’06).IEEE,2006:7-12.
[17] C′ N,NOVAKOVI′ D,MIUˇIN S,et al.Dejavu:accelerating resource allocation in virtualized environments[C]∥ACM SIGARCH Computer Architecture News.ACM,2012:423-436.
[18] TERROSO -SENZ F,VALD S-VELA M,CAMPUZANO F,et al.A complex event processing approach to perceive the vehicular context[J].Information Fusion,2015,21(1):187-209.
[19] ZOUMBOULAKIS M,ROUSSOS G.Complex event detectionin extremely resource-constrained wireless sensor networks[J].Mobile Networks and Applications,2011,16(2):194-213.
[20] YAO W,CHU C H,LI Z.Leveraging complex event processing for smart hospitals using RFID[J].Journal of Network and Computer Applications,2011,34(3):799-810.
[21] BRUNS R,DUNKEL J,MASBRUCH H,et al.Intelligent M2M:Complex event processing for machine-to-machine communication[J].Expert Systems with Applications,2015,42(3):1235-1246.
[22] WANG Y H,CAO K,ZHANG X M.Complex event processing over distributed probabilistic event streams[J].Computers & Mathematics with Applications,2013,66(10):1808-1821.
[23] MCCARTHY D R,DAYAL U.The architecture of an active data-base system[J].Proc.ACM Sigmod Conf.on Management of Data,1989,18(1):215-224.
[24] BABCOCK B,BABU S,DATAR M,et al.Models and Issues in Data Stream Systems[C]∥ ACM Sigmod-sigact-sigart Sympo-sium on Priniciples of Database Systems.2002:1-16.
[25] SHARON G,ETZION O.Event-processing network model and implementation[J].Ibm Systems Journal,2008,47(2):321-334.
[26] MANSOURI-SAMANI M,SLOMAN M.Monitoring distribu-ted systems[J].IEEE Network,1993,7(6):20-30.
[27] MANSOURI-SAMANI M,SLOMAN M.GEM:A generalized event monitoring language for distributed systems[J].Distributed Systems Engineering,1997,4(2):96-108.
[28] MEI Y,MADDEN S.Zstream:a cost-based query processor for adaptively detecting composite events[C]∥Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data.ACM,2009:193-206.
[29] CHENG S J,WANG Y J,MENG Y,et al.PMTree:An efficient pattern matching method for event stream processing[J].Journal of Computer Research and Development,2012,49(11):2481-2493.(in Chinese) 程苏珺,王永剑,孟由,等.PMTree:一种高效的事件流模式匹配方法[J].计算机研究与发展,2012,49(11):2481-2493.
[30] POTOCNIK M,JURIC M B.Towards complex event awareservices as part of soa[J].IEEE Transactions on Services Computing,2014,7(3):486-500.
[31] CUGOLA G,MARGARA A.Deployment strategies for distribu-ted complex event processing[J].Computing,2013,95(2):129-156.
[32] JAYASEKARA S,KANNANGARA S,DAHANAYAKAGE T,et al.Wihidum:Distributed complex event processing[J].Journal of Parallel and Distributed Computing,2015,s79-80:42-51.
[33] OTTENWLDER B,KOLDEHOFE B,ROTHERMEL K,etal.MCEP:a mobility-aware complex event processing system[J].ACM Transactions on Internet Technology (TOIT),2014,14(1):1-24.
[34] KAWASHIMA H,KITAGAWA H,Li X.Complex event processing over uncertain data streams[C]∥2010 International Conference on P2P,Parallel,Grid,Cloud and Internet Computing (3PGCIC).IEEE,2010:521-526.
[35] CUGOLA G,MARGARA A,MATTEUCCI M,et al.Introducing uncertainty in complex event processing:Model,implementation,and validation[J].Computing,2012,97(2):103-144.
[36] ALUR R.Formal analysis of hierarchical state machines[M]∥Verification:Theory and Practice.Springer Berlin Heidelberg,2003:42-66.

No related articles found!
Full text



No Suggested Reading articles found!