{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T08:35:44Z","timestamp":1777106144487,"version":"3.51.4"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Basic and Applied Basic Research Fund in Guangdong Province","award":["2023A1515011280"],"award-info":[{"award-number":["2023A1515011280"]}]},{"name":"Basic and Applied Basic Research Fund in Guangdong Province","award":["2022A1515010166"],"award-info":[{"award-number":["2022A1515010166"]}]},{"name":"Guangdong Talent Program","award":["2021QN02X826"],"award-info":[{"award-number":["2021QN02X826"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>In this paper, for the first time, we introduce the concepts of window-CCs and window-SCCs on undirected and directed temporal graphs, respectively. We then study the queries of window-CC and window-SCC by developing several efficient index-based query solutions. The space costs of the best indices are linear to the sizes of the temporal graphs. The extensive experimental evaluation on 12 real-world datasets demonstrates the high efficiency and effectiveness of the proposed solutions. In the future, we will develop distributed index construction algorithms, which would be useful for very large temporal graphs containing billions of edges. In the future, we will implement our algorithms by using a distributed computing platform (e.g., Pregel), which would be very useful when the temporal graph is too large to be kept by a single machine.<\/jats:p>","DOI":"10.1145\/3589315","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-27","source":"Crossref","is-referenced-by-count":14,"title":["On Querying Connected Components in Large Temporal Graphs"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-9642-428X","authenticated-orcid":false,"given":"Haoxuan","family":"Xie","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-0628-6122","authenticated-orcid":false,"given":"Yuyang","family":"Xia","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1463-814X","authenticated-orcid":false,"given":"Wensheng","family":"Luo","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-8512","authenticated-orcid":false,"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626419500099"},{"key":"e_1_2_2_2_1","doi-asserted-by":"crossref","unstructured":"G\u00e9raud Allard Philippe Jacquet and Bernard Mans. 2006. Routing in Extremely Mobile Networks. In Challenges in Ad Hoc Networking K. Al Agha I. Gu\u00e9rin Lassous and G. Pujolle (Eds.). 129--138.","DOI":"10.1007\/0-387-31173-4_15"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676869"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA575485"},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Aaron Bernstein Maximilian Probst and Christian Wulff-Nilsen. 2019. Decremental strongly-connected components and single-source reachability in near-linear time. In ACM SIGACT. 365--376.","DOI":"10.1145\/3313276.3316335"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Sandeep Bhadra and Afonso Ferreira. 2003. Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks. In Ad-Hoc Mobile and Wireless Networks Samuel Pierre Michel Barbeau and Evangelos Kranakis (Eds.). 259--270.","DOI":"10.1007\/978-3-540-39611-6_23"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13174-012-0073-z"},{"key":"e_1_2_2_8_1","volume-title":"Database Systems for Advanced Applications, Christian S","author":"Cai Tianchi","unstructured":"Tianchi Cai, Daxi Cheng, Chen Liang, Ziqi Liu, Lihong Gu, Huizhi Xie, Zhiqiang Zhang, Xiaodong Zeng, and Jinjie Gu. 2021. LinkLouvain: Link-Aware A\/B Testing and Its Application on Online Marketing Campaign. In Database Systems for Advanced Applications, Christian S. Jensen, Ee-Peng Lim, De-Nian Yang, Wang-Chien Lee, Vincent S. Tseng, Vana Kalogeraki, Jen-Wei Huang, and Chih-Ya Shen (Eds.). Springer International Publishing, Cham, 499--510."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CIBCB.2016.7758105"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40450-4_29"},{"key":"e_1_2_2_11_1","first-page":"5","article-title":"Practical Parallel Union-Find Algorithms for Transitive Closure and","volume":"17","author":"Cybenko G.","year":"1989","unstructured":"G. Cybenko, T. G. Allen, and J. E. Polito. 1989. Practical Parallel Union-Find Algorithms for Transitive Closure and Clustering. Int. J. Parallel Program., Vol. 17, 5 (oct 1989), 403--423.","journal-title":"Clustering. Int. J. Parallel Program."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SEAA.2018.00021"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3500930"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_2_15_1","volume-title":"Automata, Languages and Programming, Josep D\u00edaz, Juhani Karhum\"aki, Arto Lepist\u00f6","author":"Feigenbaum Joan","unstructured":"Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2004. On Graph Problems in a Semi-streaming Model. In Automata, Languages and Programming, Josep D\u00edaz, Juhani Karhum\"aki, Arto Lepist\u00f6, and Donald Sannella (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 531--543."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498231"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45591-4_68"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btr099"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00051-X"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207024"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66960"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1985.10011"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","unstructured":"Huan Gui Ya Xu Anmol Bhasin and Jiawei Han. 2015. Network A\/B Testing: From Sampling to Estimation. In Proceedings of the 24th International Conference on World Wide Web (Florence Italy) (WWW '15). International World Wide Web Conferences Steering Committee Republic and Canton of Geneva CHE 399--409. https:\/\/doi.org\/10.1145\/2736277.2741081","DOI":"10.1145\/2736277.2741081"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737791"},{"key":"e_1_2_2_25_1","volume-title":"Shared-Memory Parallel Algorithms for Fully Dynamic Maintenance of 2-Connected Components","author":"Haryan Chirayu Anant","unstructured":"Chirayu Anant Haryan, G Ramakrishna, Kishore Kothapalli, and Dip Sankar Banerjee. 2022. Shared-Memory Parallel Algorithms for Fully Dynamic Maintenance of 2-Connected Components. In IPDPS. IEEE, 1195--1205."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503246"},{"key":"e_1_2_2_27_1","volume-title":"Routing in Intermittently Connected Networks: Age Rumors in Connected Components. In Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerComW'07)","author":"Jacquet Philippe","year":"2007","unstructured":"Philippe Jacquet and Bernard Mans. 2007. Routing in Intermittently Connected Networks: Age Rumors in Connected Components. In Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerComW'07). 53--58."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2018.00061"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"e_1_2_2_30_1","volume-title":"Proc. Int. Conf. on World Wide Web Companion. 1343--1350","author":"Kunegis J\u00e9r\u00f4me","year":"2013","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT -- The Koblenz Network Collection. In Proc. Int. Conf. on World Wide Web Companion. 1343--1350."},{"key":"e_1_2_2_31_1","volume-title":"Introduction to algorithms","author":"Leiserson Charles Eric","unstructured":"Charles Eric Leiserson, Ronald L Rivest, Thomas H Cormen, and Clifford Stein. 1994. Introduction to algorithms. Vol. 3. MIT press."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CASON.2011.6085946"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2013.10.014"},{"key":"e_1_2_2_35_1","volume-title":"Jeffrey Xu Yu, and Qiangqiang Dai","author":"Li Rong-Hua","year":"2018","unstructured":"Rong-Hua Li, Jiao Su, Lu Qin, Jeffrey Xu Yu, and Qiangqiang Dai. 2018. Persistent community search in temporal networks. In ICDE. IEEE, 797--808."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-015-0382-1"},{"key":"e_1_2_2_37_1","volume-title":"Fast computation of dense temporal subgraphs","author":"Ma Shuai","unstructured":"Shuai Ma, Renjun Hu, Luoshu Wang, Xuelian Lin, and Jinpeng Huai. 2017. Fast computation of dense temporal subgraphs. In ICDE. IEEE, 361--372."},{"key":"e_1_2_2_38_1","unstructured":"Stuart E Madnick and Meichun Hsu. 1986. INFOPLEX research in a high-performance database computer. (1986)."},{"key":"e_1_2_2_39_1","volume-title":"Mostofa Ali Patwary","author":"Manne Fredrik","year":"2009","unstructured":"Fredrik Manne and Md. Mostofa Ali Patwary. 2009. A Scalable Parallel Union-Find Algorithm for Distributed Memory Computers. 186--195."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593661"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_2_43_1","volume-title":"International Conference on Complex Networks and Their Applications. Springer, 568--580","author":"Rannou L\u00e9o","year":"2020","unstructured":"L\u00e9o Rannou, Cl\u00e9mence Magnien, and Matthieu Latapy. 2020. Strongly connected components in stream graphs: Computation and experimentations. In International Conference on Complex Networks and Their Applications. Springer, 568--580."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544813"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90024-9"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732294"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90008-0"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.64"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_2_50_1","doi-asserted-by":"crossref","unstructured":"David Tench Evan West Victor Zhang Michael A. Bender Abiyaz Chowdhury J. Ahmed Dellas Martin Farach-Colton Tyler Seip and Kenny Zhang. 2022. GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams. In SIGMOD. ACM 325--339.","DOI":"10.1145\/3514221.3526146"},{"key":"e_1_2_2_51_1","volume-title":"A study of connectivity on dynamic graphs: computing persistent connected components. 4OR (04","author":"Vernet Mathilde","year":"2022","unstructured":"Mathilde Vernet, Yoann Pign\u00e9, and Eric Sanlaville. 2022. A study of connectivity on dynamic graphs: computing persistent connected components. 4OR (04 2022)."},{"key":"e_1_2_2_52_1","volume-title":"Efficiently Answering Span-Reachability Queries in Large Temporal Graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 1153--1164","author":"Wen Dong","year":"2020","unstructured":"Dong Wen, Yilun Huang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2020. Efficiently Answering Span-Reachability Queries in Large Temporal Graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 1153--1164."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00715-z"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-016-0246-7"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363809"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733089"},{"key":"e_1_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Yi Yang Da Yan Huanhuan Wu James Cheng Shuigeng Zhou and John CS Lui. 2016. Diversified temporal subgraph pattern mining. In SIGKDD. 1965--1974.","DOI":"10.1145\/2939672.2939848"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3485450.3485452"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:14Z","timestamp":1750178774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589315"],"URL":"https:\/\/doi.org\/10.1145\/3589315","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}