基于优先级的模式匹配中间结果管理方法

摘要

本发明公开了一种基于优先级的模式匹配中间结果管理方法，通过给时间窗口内的每个中间结果赋予一个优先级权重，在中间结果缓冲区将满时，把优先级低的中间结果存储到外存以保证事件检测的完整性，将优先级高的中间结果保留在内存，使事件检测能以更大的概率搜索到对应的模式匹配中间结果，在高效利用资源的同时达到较小的复杂事件响应时间。

主权项

1.一种基于优先级的模式匹配中间结果管理方法，其特征在于包括下述步骤：1)初始化模式匹配每个事件类型对应的实例堆栈空间，给中间结果缓冲MaxBuffer分配内存空间，并将实例堆栈和缓冲区设置为空；给优先级树T分配空间，并置为空；2)从滑动窗口W内按时间顺序读取一个事件e_i，并进行如下条件的判断：（1）如在缓冲区MaxBuffer中不存在与e_i标识相同的中间结果，则用e_i建立一个中间结果PM_Ei并存储于MaxBuffer中；（2）如在缓冲区MaxBuffer中存在与e_i标识相同的中间匹配结果PM_Ei，则将e_i的状态信息添加到中间结果PM_Ei的状态列表中，如果状态列表的状态数目达到模式E中定义的事件类型个数n，则输出事件，删除对应的中间结果，如果状态列表的状态数目未达到n，计算e_i的优先级W(e_i)＝t.e_i+(t.E_i+1-t.E_i)*P(E_i,E_i+1)，其中P(E_i,E_i+1)是一个随机变量，表示事件发生在E_i和E_i+1两个地方的概率，将W(e_i)插入到优先级树T上；E_i为复杂事件E的第i个类型的子事件，1≤i≤n，其中为事件算子，1≤i≤j，叫做E的中间匹配结果；t.e_i为事件e_i的发生的时间，t.E_i+1-t.E_i为两个相邻的事件类型的简单事件间的时间差；3)如果在缓冲区MaxBuffer中不存在与e_i标识相同的中间结果PM_Ei，但外存中存在ei对应的中间结果PM_Ei：如果MaxBuffer中的中间结果需要进行归档操作，则先将用户定义的归档区间长为R的MaxBuffer中的中间结果进行归档，归档方式为将优先级树上长度为R的优先级最低的中间结果归档到外部空间，其中R为中间结果归档区间，在MaxBuffer中预留出从数据库需要加载的中间结果的空间；将e_i对应的中间结果PM_Ei从数据库或文件系统中加载到MaxBuffer，并与e_i进行模式匹配，将e_i的状态信息更新到中间结果PM_Ei，判断是否达到输出状态，如达到输出状态，则输出事件，否则计算ei的优先级W(e_i)＝t.e_i+(t.E_i+1-t.E_i)*P(E_i,E_i+1)并将W(e_i)插入到优先级树T上；4)如果在缓冲区MaxBuffer与外存中都不存在e_i对应的中间结果PM_Ei：（1）如果e_i是待检测复杂事件的第一个类型的事件，则在中间结果集中新建一个PM_Ei，将e_i的信息记录到PM_Ei中，计算e_i的优先级，并将W(e_i)插入到优先级树T上；（2）否则，可判断不存在与e_i匹配的复杂事件，删除e_i；5)进行下一个原始事件的中间结果的处理，直到当前滑动窗口内的原始事件都被处理完毕。