CEStream:一种复杂事件流处理语言

复杂事件处理是支持大数据处理的流式计算平台的核心技术之一。CEStream语言作为一种新型的事件流处理语言,支持分布式环境下的复杂事件处理。该语言以XML等层次化数据为数据模型,为复杂事件检测提供了一种正规树模式匹配功能,并且支持结构连接和正规式匹配。同时,针对分布式的多个事件流,其能够将各个事件源模式匹配的结果按照时间顺序再一次进行正规式模式匹配,满足多源组合型复杂事件的检测需求,具有较强的事件处理能力。为了实现CEStream语言,研制了一个基于流数据处理集群和远端查询代理的执行引擎系统。该系统通过远程查询代理实现基于正规树模式的事件检测,通过流处理集群完成多源组合型复杂事件处理。实验表明,该系统实现了CEStream语言,有效地限制了各个节点之间的通信量,充分利用了集群的计算能力,整体性能能够满足应用需求。     

RFID数据流上多目标复杂事件检测

已有的RFID复杂事件处理技术主要关注于单个RFID对象的复杂事件检测和优化技术.实际上,很多RFID应用中往往需要同时检测多个同类型关联目标的复杂事件序列.研究了多个关联的RFID对象的复杂事件处理问题.通过扩展的事件语言和算子的语义以支持同类型多个RFID目标复杂事件查询的定义.通过模式的变换规则,将RFID应用中存在的各种非线性多目标复杂事件模式转换成线性模式,以便各种多目标模式在一个统一的框架下检测.提出了基于自动机NFAb2的多目标复杂事件检测模型和多目标复杂事件检测算法.通过在多目标检测算法中使用关键节点下压和同位置约束置后优化策略,大大减少了单个类型上无用实例的数目和不同类型间模式匹配的搜索空间.与SASE算法的实验比较表明算法的正确性和高效性.     

基于全集的复杂模式匹配

模式匹配是数据集成和数据转换中的重要问题.现有的模式匹配方法大多集中于发掘模式间的1:1匹配,然而,在现实世界模式之间除了1:1匹配还包括很多的复杂匹配.提出一种基于全集的复杂模式匹配方法,它可应用模式和映射的全集为被匹配模式添加信息;然后,利用多个具有特殊目的的检索程序分别对候选空间的特殊部分进行检索,发掘1:1和复杂匹配;最后通过学习全集中元素及元素间关系的统计,自动推导出可过滤候选匹配的约束,生成最优的匹配.实验表明,该方法不仅能全面地发掘模式间匹配,与其他复杂模式匹配方法相比,还具有较高的查全率和查准率.     

PMTree:一种高效的事件流模式匹配方法

复杂事件处理技术从多个持续事件流中分析并提取满足特定模式的事件序列.高吞吐率场景下,如何快速准确地识别事件序列是复杂事件处理技术中一个非常重要的问题.现在事件流的模式匹配方法——NFA、Petri网、有向图等——存在语义描述能力不足、部分算子实现代价高等缺陷.针对这一现状,设计并实现了一种基于树的模式匹配方法——PMTree.PMTree定义了事件模型及相应事件算子,将事件序列映射为树节点,同时将时间窗口约束及谓词约束等放置在相应节点,这些树节点连接成一棵PMTree来支持实时的事件筛选与过滤.进一步研究了PMTree构建过程中的优化策略,并提出了开销模型以及优化构建算法,以尽可能减少模式匹配开销.实验结果表明,相同测试条件下基于PMTree实现的复杂事件处理引擎Cesar吞吐率是基于NFA实现的开源引擎Esper的3～6倍,并且在不同事件量或事件序列复杂度下性能表现稳定.     

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

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

RFID复杂事件处理关键技术的研究与改进

RFID复杂事件处理是一个新兴的技术领域,它用来处理大量的简单事件,并从中整理出有价值的事件。RFID事件和传统的事件相比较具有海量性、空间性和时间性、数据不准确性等特征。文中在分析RFID数据特点的基础上,对RFID复杂事件处理的关键技术进行研究和改进,主要介绍RFID数据的清洗和事件检测技术。对于RFID数据清洗部分,提出了多层次过滤的方法使得到的数据更接近真实情况,而事件检测方面则提出了局部检测和全局检测相结合的方法对相关数据进行检测以得到更有意义的数据供上层应用使用。最后,对RFID复杂事件处理的发展趋势做出展望。     

基于树自动机的XML过滤技术

为了提高XML数据流的查询匹配效率,基于XML过滤技术研究提出了一种基于树自动机的XML过滤技术XTAFilter.该技术利用hash表来存储谓词,并对多个查询表达式XPath通过共享路径构建树自动机,减少了匹配的时间,提高了查询匹配的效率,同时降低系统运行时的活动状态.搭建仿真平台对技术进行验证,仿真实验结果表明,XTAFilter 技术能有效地提高XML数据流的匹配效率,提高了系统的实用性.     

基于业务逻辑分层Petri网的RFID复杂事件处理的研究

针对RFID数据不稳定性、动态性、巨量性和时空关联性等特点,为了简化RFID数据检测及处理过程,提出了面向业务逻辑分层Petri网的RFID复杂事件检测方法,给出面向业务逻辑分层的Petri网定义,同时结合纺织工业的生产特点给出基于面向业务逻辑分层Petri网的RFID复杂事件检测的具体方法。用面向RFID的复杂事件处理语言实现了设计的模型,解决了根据RFID复杂事件进一步组合成复杂事件的问题。     

基于复杂事件处理机制的RFID数据流处理方法

射频识别（RFID）数据流处理技术中基于复杂事件处理机制（CEP）的方法受到业界广泛关注。针对射频识别数据的特点以及目前射频识别复杂事件处理方法的不足,通过扩展和改进高效模式匹配算法Rete,提出了复合事件处理方法ERD。该方法实现了事件检测机制与中间结果共享机制的有机统一,从而达到了提高系统整体检测效率的目的。仿真实验证明该方法具有较好的效果。     

Ceper:一个高性能复杂事件处理引擎

复杂事件处理技术从连续的输入事件流中分析并提取出满足特定模式的事件序列。它将传统先存储静态数据再进行处理和挖掘的数据处理方法,转变为实时处理动态事件流,更加符合真实世界的数据处理模式,能够高效及时地从数据流中过滤出相对少量的具有应用价值的数据。文章设计并实现了一个高性能复杂事件处理引擎——Ceper,提出了Ceper的事件处理模型,展示了它的系统结构和模式匹配树的方法 PMT,介绍了Ceper的实现的关键技术,并进行了一定的测试。     

地铁列车环境中多依赖复杂事件处理研究

针对多源海量实时数据的复杂事件检测中，原始事件流的分流处理存在事件检测准确率低及效率慢的问题，提出一种基于事件树的复杂事件检测方法。首先给出事件依赖关系的明确定义，然后根据原子事件间存在的多依赖关系生成原子事件树，以事件树为节点构造依赖事件树链表，提升复杂事件处理引擎的有效检测次数，使得事件检测的匹配效率得到提升。同时该方法减少了事件检测过程的内存消耗，提高了事件检测的吞吐量。仿真实验与案例研究证明了提出方法在海量数据处理上的优异性及可行性。     

在线-离线数据流上复杂事件检测

随着数据采集和处理技术的发展,在物联网对象跟踪、网络监控、金融预测、电信消费模式等领域中进行事件检测显得越发重要.事件检测在一次扫描数据流的假设下完成,数据流在被处理完后丢弃.事实上,很多应用场景中,历史数据流因含有丰富的信息而不能简单丢弃,且一些事件检测查询需要同时在实时和历史数据流上进行.鉴于已有复杂事件检测很少考虑同时在实时-历史数据流上进行模式匹配,作者研究了在线-离线数据流上复杂事件检测的关键问题.主要工作如下:(1)针对滑动窗口内产生的大量模式匹配中间结果,提出利用时态关系和时空关系管理中间结果的方法 TPM和STPM.STPM以中间结果的时态和状态信息为权值对中间结果进行管理,将最近的、最有可能更新状态的中间结果置于内存,极大地减少了中间结果的读取操作代价.(2)给出了基于选择度的在线-离线复杂事件检测优化算法;(3)给出了算法的复杂性分析和代价模型;(4)在基于时空关系的中间结果管理模型下,在一个在线-离线复杂事件检测原型系统中进行实验,对多个参数(子窗口大小,选择度,匹配率,命中率)进行了算法对比分析.实验结果充分验证了所提出的算法的可行性和高效性.     

分布式复杂事件流处理平台的研究

复杂事件处理是大数据时代的关键技术之一。针对现有的复杂事件处理平台存在的各种问题,提出并设计了一个以复杂事件流处理语言CEStream为基础的分布式复杂事件流处理平台,实现了基于正规树模式的事件检测功能,支持多数据源的复杂事件处理。针对多数据源组合事件模式的检测需求,该平台可以将复杂事件分解为多个独立的事件检测任务,部署在集群中不同节点和远端的事件检测代理上。实验结果表明,系统的吞吐量和响应时间达到了预期结果,可以满足目前主流的复杂事件处理的应用需求。     

On-line rule matching for event prediction

The prediction of future events has great importance in many applications. The prediction is based on episode rules which are composed of events and two time constraints which require all the events in the episode rule and in the predicate of the rule to occur in a time interval, respectively. In an event stream, a sequence of events which matches the predicate of the rule satisfying the specified time constraint is called an occurrence of the predicate. After finding the occurrence, the consequent event which will occur in a time interval can be predicted. However, the time intervals computed from some occurrences for predicting the event can be contained in the time intervals computed from other occurrence and become redundant. As a result, how to design an efficient and effective event predictor in a stream environment is challenging. In this paper, an effective scheme is proposed to avoid matching the predicate events corresponding to redundant time intervals for prediction. Based on the scheme, we respectively consider two methodologies, forward retrieval and backward retrieval, for the efficient matching of predicate events over event streams. The approach based on forward retrieval construct a queue structure to incrementally maintain parts of the matched results as events arrive, and thus it avoids backward scans of the event stream. On the other hand, the approach based on backward retrieval maintains the recently arrived events in a tree structure. The matching of predicate events is triggered by identifiable events and achieved by an efficient retrieval on the tree structure, which avoids exhaustive scans of the arrived events. By running a series of experiments, we show that each of the proposed approaches has its advantages on particular data distributions and parameter settings.     

基于自动机的XML流多查询处理

XML流数据处理在研究领域引起广泛关注,该文针对XML流上的多查询处理提出一种算法,把多个查询合并为一个共享前缀的查询树,应用自动机和运行时栈相结合的方法,单遍扫描XML流处理数据流上的多个查询。该算法采用一种分层栈结构保存查询模式匹配候选集,利用XML节点的区间编码来确定节点之间的关系,返回整条匹配路径。     

面向中英文混合环境的多模式匹配算法

分析了中英文混合环境下多模式匹配的特点,以及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法.该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提出的算法在匹配中无需复杂的哈希运算,不需要回溯匹配指针,在中英文混合环境下能够进行正确、高效的匹配,而且不存在空间膨胀问题,具有较低的空间与时间复杂度,有较大理论与应用价值.     

InforSIB事件代数的形式化框架与代数性质

复合事件处理系统多节点处以及系统外部生成的大量的、连续到达的事件,通过规则匹配、推理等方法对事件模式进行检测,连续输出经过组合后的复合事件,以触发相应的后继处理。事件查询语言是规约事件模式的声明性语言,事件代数决定了事件查询语言的表达能力,同时也间接影响了事件检测的性能。因此,在权衡检测性能与事件查询语言的表达能力时,深入分析事件代数是非常重要的手段。基于White事件代数,扩展了事件代数的形式化框架,在形式化框架中考虑复合事件在更精细的时间关系下的语义定义,以增强事件代数的表达能力,同时考虑与应用相关的事件选择和消费策略-上下文策略,以提高事件检测的性能。讨论了InforSIB事件代数的代数性质,提出的上下文策略非常适合用于实时监控等领域,且具有良好的代数性质,保证了复合事件检测的时间和空间复杂度是有界的。     

基于语言和约束匹配器融合的元素匹配研究

在模式匹配方面已经出现了许多使用于特定应用领域的部分自动匹配方法,这种匹配方法结合了多种匹配技术以便能够在大规模的多样匹配环境中得到高的匹配率。提出了一种基于模式的元素匹配方法,它融合了语言和约束匹配器,使用了复合元素名称匹配器和神经网络匹配器,结合基于语言的匹配算法和最大优先策略的原则,以多重标准条件下复合名称匹配器的结果作为约束对模式元素进行归类。通过组合使用复合名称匹配器和神经网络匹配器,使得本方法可以应用于更复杂的匹配环境。     

Aggressive Complex Event Processing with Confidence over Out-of-Order Streams

In recent years,there has been a growing need for complex event processing (CEP),ranging from supply chain management to security monitoring.In many scenarios events are generated in different sources but arrive at the central server out of order,due to the differences of network latencies.Most state-of-the-art techniques process out-of-order events by buffering the events until the total event order within a specified range can be guaranteed.Their main problems are leading to increasing response time and reducing system throughput.This paper aims to build a high performance out-oforder event processing mechanism,which can match events as soon as they arrive instead of buffering them till all arrive.A suffix-automaton-based event matching algorithm is proposed to speed up query processing,and a confidence-based accuracy evaluation is proposed to control the query result quality.The performance of our approach is evaluated through detailed accuracy and response time analysis.As experimental results show,our approach can obviously speed up the query matching time and produce reasonable query results.