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

Efficient complex event matching algorithm based on ordered event lists

作　　者：邱涛 丁建丽 夏秀峰 郗红梅 谢沛良 周清怡 QIU Tao;DING Jianli;XIA Xiufeng;XI Hongmei;XIE Peiliang;ZHOU Qingyi(School of Computer Science,Shenyang Aerospace University,Shenyang Liaoning 110136,China;Flight Test Station,Shenyang Aircraft Industry(Group)Company Limited,Shenyang Liaoning 110034,China)

机构地区：[1]沈阳航空航天大学计算机学院,沈阳110136 [2]沈阳飞机工业(集团)有限公司试飞站/试飞实验室,沈阳110034

出　　处：《计算机应用》2023年第2期423-429,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(62002245);辽宁省教育厅基础研究项目(JYT2020027)。

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

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

分 类 号：TP315[自动化与计算机技术—计算机软件与理论]