基于有序事件列表的高效复杂事件匹配算法

doi:10.11772/j.issn.1001-9081.2021122186

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (2): 423-429.DOI: 10.11772/j.issn.1001-9081.2021122186

• 数据科学与技术 • 上一篇

基于有序事件列表的高效复杂事件匹配算法

邱涛¹(), 丁建丽¹, 夏秀峰¹, 郗红梅², 谢沛良¹, 周清怡¹

^1.沈阳航空航天大学计算机学院，沈阳 110136
^2.沈阳飞机工业（集团）有限公司试飞站/试飞实验室，沈阳 110034

收稿日期:2021-12-24 修回日期:2022-05-05 接受日期:2022-05-06 发布日期:2022-06-13 出版日期:2023-02-10
通讯作者: 邱涛
作者简介:丁建丽（1996—），女，山东青岛人，硕士研究生，主要研究方向：复杂事件处理
夏秀峰（1964—），男，山东青岛人，教授，博士，CCF会员，主要研究方向：数据库、数据仓库、数据挖掘
郗红梅（1969—），女，辽宁沈阳人，工程师，主要研究方向：遥测数据分析处理
谢沛良（1997—），男，江西赣州人，硕士研究生，主要研究方向：复杂事件处理
周清怡（1999—），男，湖北潜江人，硕士研究生，主要研究方向：复杂事件处理。
基金资助:
国家自然科学基金资助项目(62002245);辽宁省教育厅基础研究项目(JYT2020027)

Efficient complex event matching algorithm based on ordered event lists

Tao QIU¹(), Jianli DING¹, Xiufeng XIA¹, Hongmei XI², Peiliang XIE¹, Qingyi ZHOU¹

^1.School of Computer Science，Shenyang Aerospace University，Shenyang Liaoning 110136，China
^2.Flight Test Station，Shenyang Aircraft Industry （Group） Company Limited，Shenyang Liaoning 110034，China

Received:2021-12-24 Revised:2022-05-05 Accepted:2022-05-06 Online:2022-06-13 Published:2023-02-10
Contact: Tao QIU
About author:DING Jianli， born in 1996， M. S. candidate. Her research interests include complex event processing.
XIA Xiufeng， born in 1964， Ph. D.， professor. His research interests include database， data warehouse， data mining.
XI Hongmei， born in 1969， engineer. Her research interests include telemetry data analysis and processing.
XIE Peiliang， born in 1997， M. S. candidate. His research interests include complex event processing.
ZHOU Qingyi， born in 1999， M. S. candidate. His research interests include complex event processing.
Supported by:
National Natural Science Foundation of China(62002245);Basic Research Project of Educational Department of Liaoning Province(JYT2020027)

摘要/Abstract

摘要：

针对现有的复杂事件匹配处理方法存在的匹配代价高的问题，提出了一种利用事件缓冲区（有序事件列表）进行递归遍历的复杂事件匹配算法ReCEP。不同于现有方法利用自动机在事件流上进行匹配，该算法将复杂事件查询模式中的约束条件分解为不同类型，再在有序列表上对不同约束分别进行递归校验。首先，根据查询模式将相关事件实例按照事件类型进行缓存；其次，在有序列表上对事件实例执行查询过滤操作，并给出了一种基于递归遍历的算法来确定初始事件实例并且获取候选序列；最后，对候选序列的属性约束进行进一步的校验。基于股票交易模拟数据进行的实验测试和分析的结果表明，与当前主流的匹配方法SASE和Siddhi相比，ReCEP算法能够有效地减少查询匹配的处理时间，总体性能上均更优，查询匹配效率提升了8.64%以上。可见，所提出的复杂事件匹配方法能够有效提高复杂事件匹配的效率。

关键词: 复杂事件处理, 事件流, 有序事件列表, 查询过滤, 属性验证

Abstract:

Aiming at the problem of high matching cost in the existing complex event matching processing methods， a complex event matching algorithm ReCEP was proposed， which uses event buffers （ordered event lists） for recursive traversal. Different from the existing method that uses automaton to match on the event stream， this method decomposes the constraints in the complex event query mode into different types， and then recursively verifies the different constraints on the ordered list. Firstly， according to the query mode， the related event instances were cached according to the event type. Secondly， the query filtering operation was performed to the event instances on the ordered list， and an algorithm based on recursive traversal was given to determine the initial event instance and obtain candidate sequence. Finally， the attribute constraints of the candidate sequence were further verified. Experimental testing and analysis results based on simulated stock transaction data show that compared with the current mainstream matching methods SASE and Siddhi， ReCEP algorithm can effectively reduce the processing time of query matching， has overall performance better than both of the two methods， and has the query matching efficiency improved by more than 8.64%. It can be seen that the proposed complex event matching method can effectively improve the efficiency of complex event processing.

Key words: complex event processing, event stream, ordered event list, query filtering, attribute verification

中图分类号:

TP315

邱涛, 丁建丽, 夏秀峰, 郗红梅, 谢沛良, 周清怡. 基于有序事件列表的高效复杂事件匹配算法[J]. 计算机应用, 2023, 43(2): 423-429.

Tao QIU, Jianli DING, Xiufeng XIA, Hongmei XI, Peiliang XIE, Qingyi ZHOU. Efficient complex event matching algorithm based on ordered event lists[J]. Journal of Computer Applications, 2023, 43(2): 423-429.

图/表 8

图1 事件流示例

Fig.1 Example of event stream

图2 复杂事件匹配处理流程

Fig.2 Flow of complex event processing

图3 复杂事件匹配处理框架

Fig.3 Framework of complex event matching

图4 将事件实例进行过滤并划分到不同有序缓冲区

Fig.4 Event instances are filtered and divided into different ordered buffers

图5 查询过滤过程示意图

Fig.5 Schematic diagram of query filtering process

图6 属性验证过程示意图

Fig.6 Schematic diagram of attribute verification process

图7 查询模式中事件类型的个数对性能的影响

Fig.7 Influence of number of event types in query mode on performance

图8 查询模式中时间约束的大小对性能的影响

Fig.8 Influence of size of time constraint in query mode on performance

参考文献 19

1	RAHMANI A M， BABAEI Z， SOURI A. Event-driven IoT architecture for data analysis of reliable healthcare application using complex event processing［J］. Cluster Computing， 2021， 24（2）： 1347-1360. 10.1007/s10586-020-03189-w
2	何恒靖，赵伟，黄松岭.复杂事件处理技术的应用现状及展望［J］. 计算机工程， 2017， 43（1）： 20-26. 10.3969/j.issn.1000-3428.2017.01.004
	HE H J， ZHAO W， HUANG S L. Application status and prospect of complex event processing technology［J］. Computer Engineering， 2017， 43（1）： 20-26. 10.3969/j.issn.1000-3428.2017.01.004
3	产院东，郭乔进，梁中岩，等. 规则引擎发展综述［J］. 信息化研究， 2021， 47（2）：1-6.
	CHAN Y D， GUO Q J， LIANG Z Y， et al. A survey of rule engine［J］. Informatization Research， 2021， 47（2）：1-6.
4	乔雅正，程良伦，王涛，等. 地铁列车环境中多依赖复杂事件处理研究［J］. 计算机应用研究， 2019， 36（8）：2355-2358， 2367. 10.19734/j.issn.1001-3695.2018.02.0087
	QIAO Y Z， CHENG L L， WANG T， et al. Study on multi-dependency complex event processing in subway train environment［J］. Application Research of Computers， 2019， 36（8）：2355-2358， 2367. 10.19734/j.issn.1001-3695.2018.02.0087
5	王亚辉，郑联语，樊伟. 云架构下基于标准语义模型和复杂事件处理的制造车间数据采集与融合［J］. 计算机集成制造系统， 2019， 25（12）： 3103-3115. 10.13196/j.cims.2019.12.012
	WANG Y H， ZHENG L Y， FAN W. Data collection and fusion of manufacturing workshop based on standard semantic model and complex event processing under cloud architecture［J］. Computer Integrated Manufacturing Systems， 2019， 25（12）： 3103-3115. 10.13196/j.cims.2019.12.012
6	鲍军鹏，左宏良，杨科. 基于事件流的航天大数据复杂事件挖掘框架［C］// 2018软件定义卫星高峰论坛会议摘要集. 北京：软件定义卫星技术联盟， 2018： 74-80.
	BAO J P， ZUO H L， YANG K. Complex event mining framework of aerospace big data based on event flow［C］// Proceedings of the Conference Abstracts of the Software Defined Satellite Summit 2018. Beijing： Software Defined Satellite Technology Alliance， 2018： 74-80.
7	AGRAWAL J， DIAO Y L， GYLLSTROM D， et al. Efficient pattern matching over event streams［C］// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2008： 147-160. 10.1145/1376616.1376634
8	WU E， DIAO Y L， RIZVI S. High-performance complex event processing over streams［C］// Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2006： 407-418. 10.1145/1142473.1142520
9	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. New York： ACM， 2009： 193-206. 10.1145/1559845.1559867
10	Siddhi-io. Siddhi： stream processing and complex event processing engine［EB/OL］. （2015-05-12）［2021-12-23］.. 10.1145/2110486.2110493
11	GIATRAKOS N， ALEVIZOS E， ARTIKIS A， et al. Complex event recognition in the big data era： a survey［J］. The VLDB Journal， 2020， 29（1）： 313-352. 10.1007/s00778-019-00557-w
12	DIAO Y L， IMMERMAN N， GYLLSTROM D. SASE+： an agile language for Kleene closure over event streams［EB/OL］. ［2021-12-23］.. 10.1109/icde.2008.4497566
13	Threeknowbigdata. Flink_second_understand［EB/OL］. （2022-07-03）［2022-12-04］..
14	DEMERS A， GEHRKE J， HONG M S， et al. Towards expressive publish/subscribe systems［C］// Proceedings of the 2006 International Conference on Extending Database Technology， LNCS 3896. Berlin： Springer， 2006： 627-644.
15	DEMERS A， GEHRKE J， PANDA B， et al. Cayuga： a general purpose event monitoring system［EB/OL］// Proceedings of the 3rd International Conference on Innovation Database Research. ［2022-12-04］.. 10.1145/1247480.1247620
16	DOUSSON C. Extending and unifying chronicle representation with event counters［C］// Proceedings of the 15th European Conference on Artificial Intelligence. Amsterdam： IOS Press， 2002： 257-261.
17	DOUSSON C， LE MAIGAT P. Chronicle recognition improvement using temporal focusing and hierarchization［C］// Proceedings of the 2007 International Joint Conferences on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2007： 324-329.
18	LIU M， RUNDENSTEINER E A， GREENFIELD K， et al. E-Cube： multi-dimensional event sequence analysis using hierarchical pattern query sharing［C］// Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2011： 889-900. 10.1145/1989323.1989416
19	GREZ A， RIVEROS C， UGARTE M. A formal framework for complex event processing［C］// Proceedings of the 22nd International Conference on Database Theory. Dagstuhl： Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik， 2019： No.5.

[1]	张宇豪, 袁孟雯, 陆宇婧, 燕锐, 唐华锦. 面向动态事件流的神经网络转换方法[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3033-3039.
[2]	许冬冬, 袁凌云. 基于事件共享机制的物联网复杂事件处理方法[J]. 计算机应用, 2015, 35(2): 326-331.
[3]	荆心张璟李军怀. 复杂事件处理技术及其在物流物联网中的应用[J]. 计算机应用, 2013, 33(07): 2026-2030.
[4]	杜磊王文俊董存祥李力雄高珊. 基于多Agent的应急协同Petri网建模及协同检测[J]. 计算机应用, 2010, 30(10): 2567-2571.
[5]	皮明峰邓飞其. 面向制造业的RFID复杂事件处理[J]. 计算机应用, 2010, 30(10): 2768-2770.
[6]	阴晓加鞠时光王英杰. 基于复杂事件处理机制的RFID数据流处理方法[J]. 计算机应用, 2009, 29(10): 2786-2790.
[7]	江琴刘琳岚苏曦蔡轲. 基于事件权重的GUI测试路径生成方法[J]. 计算机应用, 2009, 29(05): 1382-1384.

基于有序事件列表的高效复杂事件匹配算法

Efficient complex event matching algorithm based on ordered event lists

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 19

相关文章 7

编辑推荐

Metrics