{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:37:40Z","timestamp":1778279860144,"version":"3.51.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>\n            Continuously monitoring structural patterns in streaming graphs is a critical task in many real-time graph-based applications. In this paper, we study the problem of time-constrained continuous subgraph matching (shorted as TCSM) over streaming graphs. Given a query graph\n            <jats:italic>Q<\/jats:italic>\n            with timing order constraint and a data graph stream\n            <jats:italic>G<\/jats:italic>\n            , TCSM aims to report all incremental matches of\n            <jats:italic>Q<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            for each update of\n            <jats:italic>G<\/jats:italic>\n            , where a match should obey both structure constraint (i.e., isomorphism) and timing order constraint of\n            <jats:italic>Q.<\/jats:italic>\n            Although TCSM has a wide range of applications, such as cyber-attack detection and credit card fraud detection, we note that this problem has not been well addressed. The state-of-the-art bears the limitations of high index space cost and intermediate result maintenance cost. In this paper, we propose TC-Match, an effective approach to TCSM. First, we design a space and time cost-effective index CSS, which is essentially a\n            <jats:italic>k<\/jats:italic>\n            -partite graph structure where a node corresponds to an edge in\n            <jats:italic>G.<\/jats:italic>\n            By carefully creating links between nodes, we can encapsulate into CSS the partial embedding and timing order information between edges in\n            <jats:italic>G.<\/jats:italic>\n            We theoretically show that CSS has polynomial space and construction time complexities. Second, based on the property of CSS, we develop an efficient incremental matching algorithm with an effective node merging optimization. Extensive experiments show that TC-Match can achieve up to 3 orders of magnitude query performance improvement over the baseline methods, and meanwhile the memory consumption is reduced by 48.7%-86.7%.\n          <\/jats:p>","DOI":"10.14778\/3681954.3681963","type":"journal-article","created":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T16:23:36Z","timestamp":1725035016000},"page":"2791-2804","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["TC-Match: Fast Time-Constrained Continuous Subgraph Matching"],"prefix":"10.14778","volume":"17","author":[{"given":"Jianye","family":"Yang","sequence":"first","affiliation":[{"name":"Guangzhou University, PengCheng Laboratory"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Fang","sequence":"additional","affiliation":[{"name":"Guangzhou University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhaoquan","family":"Gu","sequence":"additional","affiliation":[{"name":"Harbin Institute of Technology (Shenzhen) and PengCheng Laboratory"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ziyi","family":"Ma","sequence":"additional","affiliation":[{"name":"Hebei University of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhihong","family":"Tian","sequence":"additional","affiliation":[{"name":"Guangzhou University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,8,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. http:\/\/snap.stanford.edu\/data\/wiki-talk-temporal.html."},{"key":"e_1_2_1_2_1","unstructured":"[n.d.]. https:\/\/www.caida.org."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_4_1","volume-title":"Jan Van den Bussche, and Julia Stoyanovich","author":"Aghasadeghi Amir Pouya","year":"2023","unstructured":"Amir Pouya Aghasadeghi, Jan Van den Bussche, and Julia Stoyanovich. 2023. Temporal graph patterns by timed automata. The VLDB Journal (05 2023), 1--23."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589312"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742796"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300086"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915236"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-14-S7-S13"},{"key":"e_1_2_1_10_1","first-page":"5103","article-title":"Line Graph Neural Networks for Link Prediction","volume":"44","author":"Cai Lei","year":"2020","unstructured":"Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. 2020. Line Graph Neural Networks for Link Prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence 44 (2020), 5103--5113.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_1_11_1","volume-title":"GHunter: A Fast Subgraph Matching Method for Threat Hunting. 2023 26th International Conference on Computer Supported Cooperative Work in Design (CSCWD)","author":"Cheng Zijun","year":"2023","unstructured":"Zijun Cheng, Rujie Dai, Leiqi Wang, Ziyang Yu, Qiujian Lv, Yan Wang, and Degang Sun. 2023. GHunter: A Fast Subgraph Matching Method for Threat Hunting. 2023 26th International Conference on Computer Supported Cooperative Work in Design (CSCWD) (2023), 1014--1019."},{"key":"e_1_2_1_12_1","unstructured":"Sutanay Choudhury Lawrence Holder George Chin Khushbu Agarwal and John Feo. 2015. A selectivity based approach to continuous pattern detection in streaming graphs. (2015) 157--168."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989420"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_2_1_16_1","volume-title":"Streaming Temporal Graphs: Subgraph Matching. 2019 IEEE International Conference on Big Data (Big Data)","author":"Eric","year":"2019","unstructured":"Eric L. Goodman and Dirk Grunwald. 2019. Streaming Temporal Graphs: Subgraph Matching. 2019 IEEE International Conference on Big Data (Big Data) (2019), 4977--4986."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319880"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2013 International Conference on Management of Data.","author":"Han Wook-Shin","year":"2013","unstructured":"Wook-Shin Han, Jinsoo Lee, and Jeong-Hoon Lee. 2013. Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In Proceedings of the 2013 International Conference on Management of Data."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Frank Harary and R. Z. Norman. 1960. Some properties of line digraphs. Rendiconti del Circolo Matematico di Palermo 9 (1960) 161--168.","DOI":"10.1007\/BF02854581"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 2008 International Conference on Management of Data.","author":"He Huahai","unstructured":"Huahai He and Ambuj K. Singh. 2008. Graphs-at-a-time: query language and access methods for graph databases. In Proceedings of the 2008 International Conference on Management of Data."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588692"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457265"},{"key":"e_1_2_1_26_1","volume-title":"Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong.","author":"Kim Kyoungmin","year":"2018","unstructured":"Kyoungmin Kim, In Seo, Wook-Shin Han, Jeong-Hoon Lee, Sungpack Hong, Hassan Chafi, Hyungyu Shin, and Geonhwa Jeong. 2018. Turboflux: A fast continuous subgraph matching system for streaming graph data. In Proceedings of the 2018 International Conference on Management of Data. 411--426."},{"key":"e_1_2_1_27_1","volume-title":"Linked Stream Data Processing Engines: Facts and Figures. In International Workshop on the Semantic Web.","author":"Le-Phuoc Danh","year":"2012","unstructured":"Danh Le-Phuoc, Minh Dao-Tran, Minh-Duc Pham, Peter A. Boncz, Thomas Eiter, and Michael Fink. 2012. Linked Stream Data Processing Engines: Facts and Figures. In International Workshop on the Semantic Web."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.07.071"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3148995"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00100"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3035902"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446980"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-021-00397-0"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3363217"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457395"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0968-2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498269"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2823754"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM49781.2020.9381453"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453899"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380581"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2980257"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3425879.3425888"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551803"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523218"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCSNT.2017.8343695"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18120-2_18"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7364071"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-212864"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Jianye Yang Sheng Fang Zhaoquan Gu Ziyi Ma Xuemin Lin and Zhihong Tian. 2024. TC-Match: Fast Time-constrained Continuous Subgraph Matching. https:\/\/github.com\/Sh-Fang\/TCMatch\/blob\/main\/tcmatch_technical_report.pdf","DOI":"10.14778\/3681954.3681963"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3588695","article-title":"Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction","volume":"1","author":"Yang Rongjian","year":"2023","unstructured":"Rongjian Yang, Zhijie Zhang, Weiguo Zheng, and Jeffrey Xu Yu. 2023. Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction. Proceedings of the ACM on Management of Data 1 (2023), 1--26.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_55_1","unstructured":"Lefteris Zervakis Vinay Setty Christos Tryfonopoulos and Katja Hose. 2020. Efficient continuous multi-query processing over graph streams. (2020) 13--24."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516384"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920887"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3681954.3681963","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:30:30Z","timestamp":1725474630000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3681954.3681963"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":57,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["10.14778\/3681954.3681963"],"URL":"https:\/\/doi.org\/10.14778\/3681954.3681963","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,7]]},"assertion":[{"value":"2024-08-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}