面向时间不确定事件流的嵌套查询处理技术  

Processing Nested Query over Event Streams with Uncertain Timestamps

作　　者：刘红蕾 李芳芳 谷峪 李传文 LIU Hong-Lei LI Fang-Fang GU Yu LI Chuan-Wen(College of Computer Science and Engineering, Northeastern University, Shenyang 110819)

机构地区：[1]东北大学计算机科学与工程学院,沈阳110819

出　　处：《计算机学报》2017年第10期2271-2285,共15页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2012CB316201);国家自然科学基金(61202086;61272180);中央高校基本科研业务费(No.140404013)资助~~

摘　　要：随着复杂事件处理(Complex Event Processing,CEP)技术的发展,该技术已经在多个领域中得到了应用,例如供应链管理和智能跟踪与监控.由于嵌套查询能够满足这些应用领域里更高层次的需求,因此嵌套查询成为了CEP研究的关键问题之一,得到了广泛关注.但是,已有嵌套查询的对象都是发生时间确定的事件,并未考虑现实应用中事件的发生时间是未知的或是不精确的,而这种情况下通常需要概率的方法来表示事件的发生时间.因此文中旨在解决发生时间不确定事件流上的嵌套查询问题.首先,针对基于可能世界的基本处理方法存在的低效问题,文中提出了一种基于迭代的处理方法;进一步,在迭代处理方法的基础上,提出基于子查询长度的剪枝优化技术和基于共享子表达式的缓存优化技术,特别地,基于缓存优化技术提出了查询结果发生概率计算的剪枝方法;最后,通过实验验证了文中提出方法可有效地进行发生时间不确定事件流上的嵌套查询,并能够通过对方法的优化有效地降低处理代价,提高查询处理效率.With the development of Complex Event Processing（CEP） technology in recent years, CEP has been applied into more and more fields, such as the supply chain management and smart monitoring. Because nested query can meet some higher level of demands in these fields, as one of the important issues in CEP research, nested query arouses extensive attention. Existing work on nested pattern evaluation, however, assumes that the occurrence time of each event is known precisely, while real-world applications often render events with occurrence time unknown or imprecise which need to be modeled probabilistically. Therefore, this paper aims at processing nested CEP query over streams with uncertain timestamps. Firstly, an iteration-based method for processing nested CEP query over streams with uncertain timestamps is suggested, which improves the basic method based on the possible world model. Furthermore, two optimization methods, namely pruning based on the length of sub-queries and caching based on the sharing sub-expressions, are further explored. In addition, an efficient pruning technique to evaluate the result probability is studied based on the caching method. Finally, the experiments have verified the efficiency of the proposed methods when processing nested query over streams with uncertain timestamps.

关 键 词：事件流 时间不确定 复杂事件处理 嵌套查询 可能世界 共享子表达式 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]