APAM: Adaptive Eager-Lazy Hybrid Evaluation of Event Patterns for Low Latency

Abstract

Event pattern detection refers to identifying combinations of events matched to a user-specified query event pattern from a real-time event stream. Latency is an important measure of the performance of an event pattern detection system. Existing methods can be classified into the eager evaluation method and the lazy evaluation method depending on when each event arrival is evaluated. These methods have advantages and disadvantages in terms of latency depending on the event arrival rate. In this paper, we propose a hybrid eager-lazy evaluation method that combines the advantages of both methods. For each event type, the hybrid method, which we call APAM (Adaptive Partitioning-And-Merging), determines which method to use: eager or lazy. We also propose a formal cost model to estimate the latency and propose a method of finding the optimal partition based on the cost model. Finally, we show through experiments that our method can improve the latency by up to 361.48 times over the eager evaluation method and 27.94 times over the lazy evaluation method using a synthetic data set.