M.Sc Thesis


M.Sc StudentYankovitch Maor
SubjectHypersonic: A Hybrid Parallelization Approach for Scalable
Complex Event Processing
DepartmentDepartment of Computer Science
Supervisor PROF. Assaf Schuster


Abstract


            The ability to promptly and efficiently detect arbitrarily complex patterns in massive real-time data streams is a crucial requirement in many modern applications. The ever-growing scale of these applications and the sophistication of the patterns involved make it imperative to employ advanced solutions that can optimize pattern detection.

An effective way to achieve the above goal is to apply complex event processing (CEP) systems. These systems all detect the pattern using an algorithm that incrementally performs the detection but obviously differ in the many possible optimization avenues to do so.
One of the most prominent and well-established optimization routes is to apply CEP in a parallel manner, using a multi-core and/or a distributed environment. However, the inherent tightly coupled nature of CEP severely limits the scalability of the parallelization methods currently available.

In this thesis, we introduce a novel parallelization mechanism for efficient complex event processing over data streams. This mechanism is based on a hybrid two-tier model combining multiple layers of parallelism. By employing a fine-grained load balancing model, this multi-layered approach leads to a substantial increase in event detection throughput, while at the same time reducing the latency and the memory consumption.
 An extensive experimental evaluation on multiple real-life datasets shows that our approach consistently outperforms state-of-the-art CEP parallelization methods by a factor of two to three orders of magnitude.