An Efficient Parallel Algorithm for Complex Event Processing

Nowadays, the world is producing a tremendous amount of data every second. To consume data effectively and efficiently, researchers use scalable and reliable approaches in big data analysis to take data as inputs and process them for insights according to different purposes. CEP system is one of these processing methods. It has a wide range of applications from financial tracing to medical record cross-reference. Traditional CEP processing methods like DFS and BFS require significant memory consumption or CPU usage. Besides, most current algorithms are not optimal for parallel computation. In order to conquer those challenges, this thesis follows the latest research trend and develops an efficient parallel CEP algorithm. The algorithm divides the workload into two steps. In the first step, the algorithm calculates intermediate results and stores them in selected anchors. Then the concatenation takes place during the second step. This step demands fewer resources as the algorithm only needs to collect and append sub-paths calculated in the first step. Furthermore, the workload in two steps is fine-grained and ready to feed threads. Once each step begins, a thread pool takes a task definition with batches of workload as inputs. Finally, the algorithm proves its efficacy in experiments with refined synchronisation and communication techniques