Efficient Complete Event Trend Detection Over High-Velocity Time Series Event Streams

Complete Event Trend(CET)detection over large-scale event streams is important but challenging in various applications such as financial services,real-time business analysis,and supply chain management.A potential large number of partial intermediate results during complex event matching raise prohibitively high memory cost for the processing system.The state-of-the-art design leverages compact graph encoding.A CET is expressed as a path in the compact graph.Common sub-sequences of CETs are represented by common paths to achieve space efficiency for storing the inermediate results.However,since it needs to traverse the compact graph to insert a new event into the graph,this design needs O(n~2) time to construct a compact graph for events,leading to unacceptable latency for real-world applications.To address this problem,in this thesis,we propose a novel attribute-based indexing(ABI)graph model.The ABI graph presents events and attribute values as two types of vertices in the graph,and uses edges between event vertices and attribute vertices to represent the association between events and attribute values.We classifies the predicates by comparators and construct the ABI graph by dynamically generating attribute vertices based on both the comparators in the predicates and the attribute values of the events.Based on the continuity of edges in the graph,we design a range edge representation which uses only two edge pointers to represent all outgoing edges of an event vertices.Our design significantly reduces the CPU and memory cost of graph construction to O(log(m)) andO(1)for each event,where is the size of the attribute vertices in the graph.Based on the independence of graph construction for each event,we solve the synchronized problem of attribute vertices and propose an efficient parallel graph construction method to futher accelerate the graph construction process.In view of the high memory overhead and low CPU overhead of the BFS-based traversal algorithm and the high CPU overhead and low memory overhead of the DFS-based traversal algorithm,after the graph construction,we design an efficient parallel anchor-based traversal algorithm to combine the advantages of two basic algorithms and extract CETs from the ABI graph.To overcome the physical limitations of stand-alone systems,we futher design a broadcast-join based distributed algorithm for CET extraction.We conduct comprehensive experiments to evaluate the performance of this design.The results show that our design wins a couple of orders of magnitude back from state-of-the-art schemes.