TL;DR
This paper introduces RTECinc, an incremental approach to composite event recognition in streaming data. By intelligently updating only affected queries instead of recomputing everything from scratch, RTECinc significantly speeds up reasoning in dynamic environments with delayed or revised events, outperforming its predecessor RTEC.
What Problem Does This Paper Address?
In real-time streaming applications, data often arrives with delays or is subject to revisions. Composite Event Recognition (CER) systems, like the Event Calculus for Run-Time Reasoning (RTEC), are designed to detect complex patterns formed by simpler events. However, RTEC's standard approach of re-evaluating all queries from scratch whenever new data arrives, even if it only affects a small portion of the data, leads to significant inefficiencies. This is particularly problematic in domains like maritime surveillance where data streams are continuous and subject to communication lags or sensor corrections. The paper addresses this by developing an incremental method that avoids redundant computations when handling delayed or revised events.
Methods
The core innovation is RTECinc, an incremental version of RTEC. Instead of recomputing all composite event (CE) intervals from scratch at each query time, RTECinc focuses on updating only the affected queries. This is achieved through a two-phase process: deletion and addition. The "addition phase," detailed in this paper, focuses on calculating new initiation and termination points for simple fluents. This involves using "delta rules" that efficiently re-evaluate only the parts of the rules that could have been affected by new or retracted events. These delta rules leverage specific sets of events and intervals (e.g., events that arrived at the current query time, or events that were retracted) to perform localized updates, thereby reducing computational complexity compared to RTEC's full re-computation.
Datasets
The paper mentions experiments conducted on two types of datasets:
- A publicly available dataset concerning vessels sailing in the Atlantic Ocean near Brest, France.
- A dataset concerning vessels sailing in European seas.
For the first dataset, artificial delays were injected to simulate scenarios where 40% of events are delayed. The second dataset utilizes natural delays. The authors state that the code for RTECinc and some of the employed datasets are publicly available to ensure reproducibility.
Key Insights and Ideas
- The inefficiency of full re-computation: The paper clearly demonstrates that re-calculating all composite event intervals from scratch, even when only a few events are delayed or revised, is computationally wasteful.
- Incremental updates are key: By focusing on updating only the affected queries, RTECinc achieves significant performance gains. This highlights the power of localized reasoning in dynamic systems.
- Delta rules for targeted updates: The introduction of delta rules provides a formal mechanism to efficiently incorporate new or retracted events into the existing reasoning process, without disturbing unaffected parts.
- Handling delays and revisions efficiently: RTECinc's ability to manage variable delays and event revisions incrementally is crucial for practical real-time streaming applications.
Key Results
The empirical analysis shows that RTECinc consistently outperforms RTEC in terms of average recognition time across both synthetic and natural delay datasets.
- For synthetic delays (Figure 3a), RTECinc achieved performance gains ranging from approximately 44% to 80% depending on the window size.
- For natural delays (Figure 3b), the gains were between approximately 18% and 82%. The paper also notes that RTECinc exhibits more predictable performance, indicated by smaller standard deviations, which is valuable for real-time systems. These results are consistent with the theoretical complexity analysis presented in the original paper.
Limitations and Future Work
- Focus on simple fluents: This extended abstract primarily details the incremental treatment of simple fluents. The paper mentions that the full details of both deletion and addition phases, as well as the treatment of statically determined fluents, can be found in the original paper [Tsilionis et al., 2022].
- Original paper for full details: The authors explicitly refer to their original publication for a more comprehensive treatment of the incremental procedure and statically determined fluents.
- Future work: Not explicitly detailed in this extended abstract, but the success of RTECinc suggests potential for broader application in complex event processing systems facing similar challenges.
Summary updated