{"created":"2025-01-19T01:44:23.863957+00:00","updated":"2025-01-19T08:01:32.479901+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00240286","sets":["934:1022:11484:11723"]},"path":["11723"],"owner":"44499","recid":"240286","title":["Efficient Pattern Matching over Out-of-Order Event Streams Using Sliding Buffer"],"pubdate":{"attribute_name":"公開日","attribute_value":"2024-10-22"},"_buckets":{"deposit":"bcafa2be-5064-4dfd-a3aa-6024c23dc0a7"},"_deposit":{"id":"240286","pid":{"type":"depid","value":"240286","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Efficient Pattern Matching over Out-of-Order Event Streams Using Sliding Buffer","author_link":["658945","658949","658946","658947","658948","658944"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Efficient Pattern Matching over Out-of-Order Event Streams Using Sliding Buffer"},{"subitem_title":"Efficient Pattern Matching over Out-of-Order Event Streams Using Sliding Buffer","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[研究論文] pattern matching, out-of-order event stream, incremental sliding-window, sliding buffer, complex event processing","subitem_subject_scheme":"Other"}]},"item_type_id":"3","publish_date":"2024-10-22","item_3_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Science and Technology, University of Tsukuba／Department of Computer Science, IPB University"},{"subitem_text_value":"Center for Computational Sciences, University of Tsukuba"},{"subitem_text_value":"Center for Computational Sciences, University of Tsukuba"}]},"item_3_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Science and Technology, University of Tsukuba / Department of Computer Science, IPB University","subitem_text_language":"en"},{"subitem_text_value":"Center for Computational Sciences, University of Tsukuba","subitem_text_language":"en"},{"subitem_text_value":"Center for Computational Sciences, University of Tsukuba","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/240286/files/IPSJ-TOD1704002.pdf","label":"IPSJ-TOD1704002.pdf"},"date":[{"dateType":"Available","dateValue":"2026-10-22"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-TOD1704002.pdf","filesize":[{"value":"2.0 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"13"},{"tax":["include_tax"],"price":"0","billingrole":"39"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"8f047641-3b60-4c3d-822b-162c548bd35b","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2024 by the Information Processing Society of Japan"}]},"item_3_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Rina, Trisminingsih"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Savong, Bou"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Toshiyuki, Amagasa"}],"nameIdentifiers":[{}]}]},"item_3_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Rina, Trisminingsih","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Savong, Bou","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Toshiyuki, Amagasa","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_3_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AA11464847","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_3_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7799","subitem_source_identifier_type":"ISSN"}]},"item_3_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"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.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.32(2024) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.32(2024) (online)\n------------------------------","subitem_description_type":"Other"}]},"item_3_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌データベース（TOD）"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2024-10-22","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"4","bibliographicVolumeNumber":"17"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":240286,"links":{}}