High-Performance Complex Event Matching over Out-of-Order Event Streams
摘要
Matching complex events in out-of-order event streams has gained significant attention due to its inherent challenges. Existing methods generally fall into two main categories. One approach restores the order of out-of-order events to ensure correct matching, but this comes with high reordering costs. The other approach processes out-of-order events directly, avoiding reordering costs by adjusting the results with late-arriving events, though it cannot guarantee correctness. In this paper, we propose an efficient method that sorts only parts of the event stream while still ensuring correctness. The key observation is that sorting is necessary only for out-of-order events that could affect the complex event results. To achieve this, we use bucket sorting to organize out-of-order events into ordered event buckets and then perform the matching over these buckets. We further design a hash structure-based bucket to ensure accurate matching within each bucket. Experimental evaluations on various datasets demonstrate that our method significantly improves matching efficiency compared to existing approaches.