论文部分内容阅读
随着无线射频识别(Radio Frequency Identification, RFID)、传感器等电子数据采集设备(Electronic Data Gathering Equipment, EDGE)的不断发展,产生了空前的海量数据。由于复杂事件检测技术能够帮助人们从这些海量数据中获取其所需信息,因而近年来受到了广泛关注与研究。那些传统的方法大多是通过建立某种内存数据结构,并采用某种能够减少中间结果的优化策略,从而达到对一段较短时间内发生的复杂事件进行检测的目的。然而,现实生活中,除了这种在短期内即可发生的复杂事件之外,还存在许多复杂事件,从它们开始发生到其完全结束需要花费很长时间。换言之,人们周围还存在着许多符合长过程特点的事件流。由于内存的限制,采用传统的复杂事件检测技术不能够对这种事件流进行处理,而且目前几乎还没有针对长过程事件流进行复杂事件检测的相关研究成果,因此对长过程复杂事件检测技术的研究迫在眉睫。为实现面向长过程的复杂事件检测,本文以传统复杂事件检测方法为基础,结合长过程事件流自身的特点建立了一系列数据结构,并基于这些结构提出了一套支持长过程复杂事件检测的方法。本文的研究重点在于实现长过程情形事件实例高效的内外存调度,另外还提出了能够加速复杂事件检测进行的算法,主要贡献如下:首先,为了存储随长过程事件流到达的事件实例,提出了TSH (Hash by object ID based on timeslice model)实例存储策略。它能够为进行长过程复杂事件检测提供有规律的事件实例。其次,基于TSH策略,提出了一种称为实例映射结构的数据结构来帮助查找所需实例。由于它起到了对先前所有事件实例的存储位置进行索引的作用,因此本文通过实例映射结构和TSH策略的结合实现了候选实例高效的内外存调度算法。再次,为匹配过程提出了增量匹配方法。在时间戳前缀数组的帮助下,该方法通过共享子序列直接输出结果序列,从而达到了加速匹配过程进行的目的,进而加速了整个复杂事件检测过程的进行。最后,通过将上述方法进行扩展,实现了滑动窗口情形下的长过程复杂事件检测。通过理论分析和实验评估,证明了本文提出的长过程复杂事件检测方法符合理论上的可行性和操作上的高效与正确性。