基于层次自动机模型的复杂事件层次实现研究

doi:10.11896/j.issn.1002-137X.2017.07.028

摘要/Abstract

摘要： 复杂事件处理技术从数据流中提取满足特定模式的事件序列,具有实时、海量、智能的特点,近年来引起了学术界和商业界的广泛关注。但是,之前的工作侧重于对单层复杂事件检测的研究。事实上,由于业务系统对信息有不同层次的需求,需要对事件进行分层处理,单层复杂事件检测并不能充分支持事件分层的需求。针对这种情况,在事件层次概念以及传统NFA模型的基础上,定义了分层复杂事件检测模型层次自动机NHA,基于NHA模型设计了更为直观高效的EH-Tree结构,并给出了分层复杂事件检测HCED算法和代价模型。最后以吞吐量和内存占用为指标,进行了大量的实验,对比并分析了HCED算法与传统基于NFA模型的SASE算法的时间性能和空间性能。实验结果表明,HCED算法能有效且高效地实现分层复杂事件检测,填补了CEP不支持分层复杂事件检测的空白,为下一步研究提供了基础。

关键词: 复杂事件处理,模式匹配,事件层次,层次自动机,树

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

金大卫,施斯,易彩,杨兵. 基于层次自动机模型的复杂事件层次实现研究[J]. 计算机科学, 2017, 44(7): 151-160. https://doi.org/10.11896/j.issn.1002-137X.2017.07.028

JIN Da-wei, SHI Si, YI Cai and YANG Bing. Study of Complex Event Hierarchies Realization Based on Hierarchical Automata Model[J]. Computer Science, 2017, 44(7): 151-160. https://doi.org/10.11896/j.issn.1002-137X.2017.07.028

参考文献

[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,ethz.ch/www,dbis.ethz.ch/education/ws0708/adv_top_infsyst/papers/sase_tr07.pdf.
[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed