{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:46Z","timestamp":1779174946743,"version":"3.51.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"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,12,18]]},"abstract":"<jats:p>Connectivity query processing is a fundamental problem in graph processing. Given an undirected graph and two query vertices, the problem aims to identify whether they are connected via a path. Given frequent edge updates in real graph applications, in this paper, we study connectivity query processing in fully dynamic graphs, where edges are frequently inserted or deleted. A recent solution, called D-tree, maintains a spanning tree for each connected component and applies several heuristics to reduce the depth of the tree. To improve the efficiency, we propose a new spanning-tree-based solution by maintaining a disjoint-set tree simultaneously. By combining the advantages of two trees, we achieve the constant query time complexity and also significantly improve the theoretical running time in both edge insertion and edge deletion. Our performance studies on real large datasets show considerable improvement of our algorithms.<\/jats:p>","DOI":"10.1145\/3698805","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:40:35Z","timestamp":1734712835000},"page":"1-23","source":"Crossref","is-referenced-by-count":2,"title":["Constant-time Connectivity Querying in Dynamic Graphs"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9846-8629","authenticated-orcid":false,"given":"Lantian","family":"Xu","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6068-5062","authenticated-orcid":false,"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Ronghua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2674-1638","authenticated-orcid":false,"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiaotong University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,20]]},"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":"publisher","DOI":"10.1109\/TKDE.2009.117"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551868"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-32-9042-6_17"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225269"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/320211.320215"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276715"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_10_1","volume-title":"TheoretiCS","volume":"2","author":"Huang Shang-En","year":"2023","unstructured":"Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. 2023. Fully Dynamic Connectivity in O(\u0142og n (\u0142oglog n)^2) Amortized Expected Time. TheoretiCS, Vol. 2 (2023)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/945394.945398"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_13_1","volume-title":"DBL: Efficient Reachability Queries on Dynamic Graphs. In Database Systems for Advanced Applications: 26th International Conference, DASFAA","author":"Lyu Qiuyi","year":"2021","unstructured":"Qiuyi Lyu, Yuchen Li, Bingsheng He, and Bin Gong. 2021. DBL: Efficient Reachability Queries on Dynamic Graphs. In Database Systems for Advanced Applications: 26th International Conference, DASFAA 2021, Taipei, Taiwan, April 11--14, 2021, Proceedings, Part II 26. Springer, 761--777."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSAA.2016.52"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Zijun Mao Hong Yao Qi Zou Weiting Zhang Ying Dong et al. 2021. Digital contact tracing based on a graph database algorithm for emergency management during the COVID-19 epidemic: Case study. JMIR mHealth and uHealth Vol. 9 1 (2021) e26836.","DOI":"10.2196\/26836"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021819901281"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1186\/1756-0381-4-10"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0288-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","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: 9th International Conference on Extending Database Technology Heraklion Crete Greece March 14--18 2004 9. Springer 237--255.","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.57"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654960"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715896"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335345"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732992"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00104"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00715-z"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00193"},{"key":"e_1_2_1_32_1","volume-title":"Reachability Labeling for Distributed Graphs. In 38th IEEE International Conference on Data Engineering, ICDE 2022","author":"Zhang Junhua","year":"2022","unstructured":"Junhua Zhang, Wentao Li, Lu Qin, Ying Zhang, Dong Wen, Lizhen Cui, and Xuemin Lin. 2022. Reachability Labeling for Distributed Graphs. In 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9--12, 2022. IEEE, 686--698."},{"key":"e_1_2_1_33_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\/3698805","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698805","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:46:27Z","timestamp":1774979187000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698805"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,18]]}},"alternative-id":["10.1145\/3698805"],"URL":"https:\/\/doi.org\/10.1145\/3698805","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]}}}