{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:18:51Z","timestamp":1773825531408,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>We study the historical connectivity query in temporal graphs where edges continuously arrive. Given an arbitrary time window, and two query vertices, the problem aims to identify if two vertices are connected by a path in the snapshot of the window. The state-of-the-art method designs an index based on the two-hop cover, and updating the index is costly when new edges arrive. In this paper, we propose a new framework and design a novel forest-based index for historical connectivity queries. The index enables us to answer queries by searching if two vertices are connected in the forest. We update the index by modifying a forest structure. Our techniques also work for connectivity query processing in a sliding window of temporal graphs. Extensive experiments have been conducted to show the considerable advantages of our approach compared with the state-of-the-art methods in both historical connectivity queries and sliding-window connectivity queries.<\/jats:p>","DOI":"10.1145\/3654960","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-25","source":"Crossref","is-referenced-by-count":6,"title":["On Querying Historical Connectivity in Temporal Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-3821-8406","authenticated-orcid":false,"given":"Jingyi","family":"Song","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0903-1503","authenticated-orcid":false,"given":"Dong","family":"Wen","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9846-8629","authenticated-orcid":false,"given":"Lantian","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6068-5062","authenticated-orcid":false,"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6572-2600","authenticated-orcid":false,"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney, NSW, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiaotong University, Shanghai, China"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/66926.66950"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Kemafor Anyanwu and Amit Sheth. 2003. \u03c1-Queries: enabling querying for semantic associations on the semantic web. In WWW. 690--699.","DOI":"10.1145\/775152.775249"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.117"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.10.005"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551868"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545503"},{"key":"e_1_2_1_8_1","volume-title":"Stubbs","author":"Crouch Michael S.","year":"2013","unstructured":"Michael S. Crouch, Andrew McGregor, and Daniel M. Stubbs. 2013. Dynamic Graphs in the Sliding-Window Model. In ESA (Lecture Notes in Computer Science, Vol. 8125). 337--348."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Xiangyang Gou and Lei Zou. 2021. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. In SIGMOD. 645--657.","DOI":"10.1145\/3448016.3452800"},{"key":"e_1_2_1_10_1","volume-title":"Henzinger and Valerie King","author":"Monika","year":"1997","unstructured":"Monika R. Henzinger and Valerie King. 1997. Maintaining minimum spanning trees in dynamic graphs. In Automata, Languages and Programming, Pierpaolo Degano, Roberto Gorrieri, and Alberto Marchetti-Spaccamela (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 594--604."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327209"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039718"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Ruoming Jin Yang Xiang Ning Ruan and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD. 595--608.","DOI":"10.1145\/1376616.1376677"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627898"},{"key":"e_1_2_1_18_1","volume-title":"Renata Borovica-Gajic, Zhiqiong Wang, Junchang Xin, and Jianxin Li.","author":"Li Mo","year":"2020","unstructured":"Mo Li, Farhana Murtaza Choudhury, Renata Borovica-Gajic, Zhiqiong Wang, Junchang Xin, and Jianxin Li. 2020. CrashSim: An Efficient Algorithm for Computing SimRank over Static and Temporal Graphs. In ICDE. IEEE, 1141--1152."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--73197--7_52"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2196\/26836"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_22_1","volume-title":"Tamer \u00d6 zsu","author":"Pacaci Anil","year":"2020","unstructured":"Anil Pacaci, Angela Bonifati, and M. Tamer \u00d6 zsu. 2020. Regular Path Query Evaluation on Streaming Graphs. In SIGMOD. 1415--1430."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1186\/1756-0381-4-10"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/13093618X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2019.00108"},{"key":"e_1_2_1_27_1","volume-title":"HOPI: An Efficient Connection Index for Complex XML Document Collections. In Advances in Database Technology - EDBT","author":"Schenkel Ralf","year":"2004","unstructured":"Ralf Schenkel, Anja Theobald, and Gerhard Weikum. 2004. HOPI: An Efficient Connection Index for Complex XML Document Collections. In Advances in Database Technology - EDBT 2004, Elisa Bertino, Stavros Christodoulakis, Dimitris Plexousakis, Vassilis Christophides, Manolis Koubarakis, Klemens B\u00f6hm, and Elena Ferrari (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 237--255."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.57"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006--5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802464"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715896"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0468-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00104"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00715-z"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589315"},{"key":"e_1_2_1_37_1","volume-title":"Zaki","author":"Yildirim Hilmi","year":"2013","unstructured":"Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. 2013. DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs. CoRR, Vol. abs\/1301.0977 (2013). showeprint[arXiv]1301.0977 http:\/\/arxiv.org\/abs\/1301.0977"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--1--4419--6045-0_6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476260"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654960","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654960","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:42:20Z","timestamp":1755787340000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654960"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654960"],"URL":"https:\/\/doi.org\/10.1145\/3654960","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}