Event Pattern Matching over Graph Streams

A graph is a fundamental and general data structure underlying all data applications. Many applications today call for the manage-ment and query capabilities directly on graphs. Real time graph streams, as seen in road networks, social and communication net-works, and web requests, are such applications. Event pattern matching requires the awareness of graph structures, which is different from traditional complex event processing. It also re-quires a focus on the dynamicity of the graph, time order con-straints in patterns, and online query processing, which deviates significantly from previous work on subgraph matching as well. We study the semantics and efficient online algorithms for this important and intriguing problem, and evaluate our approaches with extensive experiments over real world datasets in four differ-ent domains. 1