PCG: An Efficient Method for Composite Pattern Matching over Data Streams

Sequential data segments in data streams are very meaningful in many areas. These data segments usually have complicated appearance and require online processing. But matching these data segments can be time-consuming and there are multiple matching tasks to be proceeded simultaneously. This paper presents a novel data structurepattern combination graph (PCG) and corresponding algorithms to accomplish composite pattern matching over data streams. To make it possible to deal with complicated patterns efficiently, PCG firstly identify similar segments among different segments as basic patterns, and then deal with the composite semantics between basic patterns. In this way, data stream flow into PCG for matching in the form of basic patterns. Later procedures are operated according to the types of nodes in PCG and the final results are returned to users. From the perspective of recall ratio, precision ratio and efficiency, the experimental results on real data sets of medical streams show that PCG is feasible and effective.