Efficient Pattern Matching over Out-of-Order Event Streams Using Sliding Buffer

• Item type: Trans(1)
• 公開日: 2024-10-22
• タイトル: Efficient Pattern Matching over Out-of-Order Event Streams Using Sliding Buffer
• タイトル / 言語: en
• タイトル: Efficient Pattern Matching over Out-of-Order Event Streams Using Sliding Buffer
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [研究論文] pattern matching, out-of-order event stream, incremental sliding-window, sliding buffer, complex event processing
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Graduate School of Science and Technology, University of Tsukuba／Department of Computer Science, IPB University
• 著者所属: Center for Computational Sciences, University of Tsukuba
• 著者所属: Center for Computational Sciences, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Technology, University of Tsukuba / Department of Computer Science, IPB University
• 著者所属(英): en
• 著者所属(英): Center for Computational Sciences, University of Tsukuba
• 著者所属(英): en
• 著者所属(英): Center for Computational Sciences, University of Tsukuba
• 著者名: Rina, Trisminingsih; Savong, Bou; Toshiyuki, Amagasa
• 著者名(英): Rina, Trisminingsih; Savong, Bou; Toshiyuki, Amagasa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Pattern matching over event streams has been widely used in many modern applications. A key technology tailored for pattern matching in streaming settings is Complex Event Processing (CEP). The most common CEP-based systems assume that input events arrive in total order based on their occurrence timestamps. However, this assumption fails in real-world applications for several reasons, such as network latency, machine failure, causing out-of-order events. Consequently, the current CEP systems face challenges to ensure accuracy and timeliness in pattern matching. To solve this problem, a number of out-of-order event stream handling approaches have been proposed. This paper introduces a new approach to out-of-order event stream handling for nondeterministic finite automaton (NFA)-based pattern matching. The key idea is to employ a sliding buffer structure that utilizes the sliding window concept and temporal indexing to incrementally evaluate the predefined pattern over streams. Further, we present a new matching algorithm that supports an invalidation mechanism for incorrect prior pattern matches affected by out-of-order events. We conduct extensive experimentation with synthetic and real-world datasets, and the results confirm that our proposed approach can deal with out-of-order event streams in pattern matching better than the state-of-the-art approach, especially in computational latency.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.32(2024) (online); ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Pattern matching over event streams has been widely used in many modern applications. A key technology tailored for pattern matching in streaming settings is Complex Event Processing (CEP). The most common CEP-based systems assume that input events arrive in total order based on their occurrence timestamps. However, this assumption fails in real-world applications for several reasons, such as network latency, machine failure, causing out-of-order events. Consequently, the current CEP systems face challenges to ensure accuracy and timeliness in pattern matching. To solve this problem, a number of out-of-order event stream handling approaches have been proposed. This paper introduces a new approach to out-of-order event stream handling for nondeterministic finite automaton (NFA)-based pattern matching. The key idea is to employ a sliding buffer structure that utilizes the sliding window concept and temporal indexing to incrementally evaluate the predefined pattern over streams. Further, we present a new matching algorithm that supports an invalidation mechanism for incorrect prior pattern matches affected by out-of-order events. We conduct extensive experimentation with synthetic and real-world datasets, and the results confirm that our proposed approach can deal with out-of-order event streams in pattern matching better than the state-of-the-art approach, especially in computational latency.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.32(2024) (online); ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 17, 号 4, 発行日 2024-10-22
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会