Out-of-Order Event Stream Matching Based on Partial Ordering

The problem of complex event matching in out-of-order event streams has garnered significant attention. Existing approaches can generally be classified into two categories: one that restores the order of events to ensure matching accuracy, but at the cost of substantial sorting overhead; and another that directly processes out-of-order events, relying on delayed events to adjust the results, thus avoiding the reordering cost, but without guaranteeing the precision of the outcomes. In this paper, we present an effective solution that requires only partial ordering of the event stream and leverages a more efficient automaton-based matching process, significantly reducing both sorting and matching costs. The key insight of our work is that, in the context of complex event matching, correctness in matching only necessitates certain events to maintain a specific sequential relationship, while other events can be out-of-order. To achieve this, we organize the event stream into continuous ordered event sets, where internal ordering within each set is not required, but the sequential relationships between these sets allow for the derivation of a substantial number of matching results. Although some results may be lost in the process, the proposed approach is well-suited for practical applications where high precision is not a critical requirement. Experimental evaluations on multiple datasets demonstrate that our method significantly improves matching efficiency compared to existing techniques.