{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T15:21:20Z","timestamp":1771600880330,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>Many real-world graphs, e.g., social networks, biological networks, knowledge graphs, naturally come with edge-labels, with different labels representing different relationships between nodes. On such edge-labeled graphs, an important query is the<jats:italic>label-constrained reachability (LCR)<\/jats:italic>query, where we are given a source<jats:italic>s<\/jats:italic>, a target<jats:italic>t<\/jats:italic>, a label set \u03c8, and the goal is to check if there exists any path<jats:italic>P<\/jats:italic>from<jats:italic>s<\/jats:italic>to<jats:italic>t<\/jats:italic>such that labels of edges on<jats:italic>P<\/jats:italic>all belong to \u03c8. Existing indexing schemes for LCR queries still focus on static graphs, despite the fact that many edge-labeled graphs are dynamic in nature.<\/jats:p><jats:p>Motivated by the limitations of existing solutions, we present a study on how to effectively maintain the indexing scheme on dynamic graphs. Our proposed approach is based on the state-of-the-art 2-hop index for LCR queries. In this paper, we present efficient algorithms for updating the index structure in response to dynamic edge insertions\/deletions and demonstrate the correctness of our update algorithms. Following that, we present that adopting a query-friendly but update-unfriendly indexing scheme results in surprisingly superb query\/update efficiency and outperforms those update-friendly ones. We analyze and demonstrate that the query-friendly indexing scheme actually achieves the same time complexity as those of update-friendly ones. Finally, we present the batched update algorithms where the updates may include multiple edge insertions\/deletions. Extensive experiments show the effectiveness of the proposed update algorithms, query-friendly indexing scheme, and batched update algorithms.<\/jats:p>","DOI":"10.14778\/3529337.3529348","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:23:05Z","timestamp":1655936585000},"page":"1645-1657","source":"Crossref","is-referenced-by-count":26,"title":["DLCR"],"prefix":"10.14778","volume":"15","author":[{"given":"Xin","family":"Chen","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"You","family":"Peng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Sibo","family":"Wang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_3_1","volume-title":"Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5","author":"Angles Renzo","year":"2017","unstructured":"Renzo Angles , Marcelo Arenas , Pablo Barcel\u00f3 , Aidan Hogan , Juan L. Reutter , and Domagoj Vrgoc . 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5 ( 2017 ), 68:1--68:40. Renzo Angles, Marcelo Arenas, Pablo Barcel\u00f3, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. 2017. Foundations of Modern Query Languages for Graph Databases. ACM Comput. Surv. 50, 5 (2017), 68:1--68:40."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.117"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516417"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365652"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_2_1_11_1","unstructured":"Alastair Green Martin Junghanns Max Kie\u00dfling Tobias Lindaaker Stefan Plantikow and Petra Selmer. 2018. openCypher: New Directions in Property Graph Querying. In EDBT. 520--523. Alastair Green Martin Junghanns Max Kie\u00dfling Tobias Lindaaker Stefan Plantikow and Petra Selmer. 2018. openCypher: New Directions in Property Graph Querying. In EDBT. 520--523."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Monika Rauch Henzinger and Valerie King. 1995. Fully Dynamic Biconnectivity and Transitive Closure. In FOCS. 664--672. Monika Rauch Henzinger and Valerie King. 1995. Fully Dynamic Biconnectivity and Transitive Closure. In FOCS. 664--672.","DOI":"10.1109\/SFCS.1995.492668"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807183"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929941"},{"key":"e_1_2_1_15_1","unstructured":"Ruoming Jin Yang Xiang Ning Ruan and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD. 595--608. Ruoming Jin Yang Xiang Ning Ruan and Haixun Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In SIGMOD. 595--608."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1227161.1370597"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"J\u00e9r\u00f4me Kunegis. 2013. KONECT: the Koblenz network collection. In WWW. 1343--1350. J\u00e9r\u00f4me Kunegis. 2013. KONECT: the Koblenz network collection. In WWW. 1343--1350.","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_18_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data. Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446099"},{"key":"e_1_2_1_20_1","volume-title":"Answering Reachability and K-Reach Queries on Large Graphs with Label-Constraints. The VLDB Journal","author":"Peng You","year":"2021","unstructured":"You Peng , Xuemin Lin , Ying Zhang , Wenjie Zhang , and Lu Qin . 2021. Answering Reachability and K-Reach Queries on Large Graphs with Label-Constraints. The VLDB Journal ( 2021 ), 1--25. You Peng, Xuemin Lin, Ying Zhang, Wenjie Zhang, and Lu Qin. 2021. Answering Reachability and K-Reach Queries on Large Graphs with Label-Constraints. The VLDB Journal (2021), 1--25."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3481978"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Liam Roditty. 2013. Decremental maintenance of strongly connected components. In SODA. 1143--1150. Liam Roditty. 2013. Decremental maintenance of strongly connected components. In SODA. 1143--1150.","DOI":"10.1137\/1.9781611973105.82"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Liam Roditty and Uri Zwick. 2004. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In STOC. 184--191. Liam Roditty and Uri Zwick. 2004. A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In STOC. 184--191.","DOI":"10.1145\/1007352.1007387"},{"key":"e_1_2_1_25_1","unstructured":"Ralf Schenkel Anja Theobald and Gerhard Weikum. 2005. Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections. In ICDE. 360--371. Ralf Schenkel Anja Theobald and Gerhard Weikum. 2005. Efficient Creation and Incremental Maintenance of the HOPI Index for Complex XML Document Collections. In ICDE. 360--371."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Lucien D. J. Valstar George H. L. Fletcher and Yuichi Yoshida. 2017. Landmark Indexing for Evaluation of Label-Constrained Reachability Queries. In SIGMOD. 345--358. Lucien D. J. Valstar George H. L. Fletcher and Yuichi Yoshida. 2017. Landmark Indexing for Evaluation of Label-Constrained Reachability Queries. In SIGMOD. 345--358.","DOI":"10.1145\/3035918.3035955"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Sarisht Wadhwa Anagh Prasad Sayan Ranu Amitabha Bagchi and Srikanta Bedathur. 2019. Efficiently Answering Regular Simple Path Queries on Large Labeled Networks. In SIGMOD. 1463--1480. Sarisht Wadhwa Anagh Prasad Sayan Ranu Amitabha Bagchi and Srikanta Bedathur. 2019. Efficiently Answering Regular Simple Path Queries on Large Labeled Networks. In SIGMOD. 1463--1480.","DOI":"10.1145\/3299869.3319882"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Sibo Wang Wenqing Lin Yi Yang Xiaokui Xiao and Shuigeng Zhou. 2015. Efficient Route Planning on Public Transportation Networks: A Labelling Approach. In SIGMOD. ACM 967--982. Sibo Wang Wenqing Lin Yi Yang Xiaokui Xiao and Shuigeng Zhou. 2015. Efficient Route Planning on Public Transportation Networks: A Labelling Approach. In SIGMOD. ACM 967--982.","DOI":"10.1145\/2723372.2749456"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3015274.3015277"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"},{"key":"e_1_2_1_32_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 abs\/1301.0977 (2013). Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. 2013. DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs. CoRR abs\/1301.0977 (2013)."},{"key":"e_1_2_1_33_1","unstructured":"Andy Diwen Zhu Wenqing Lin Sibo Wang and Xiaokui Xiao. 2014. Reachability queries on large dynamic graphs: a total order approach. In SIGMOD. 1323--1334. Andy Diwen Zhu Wenqing Lin Sibo Wang and Xiaokui Xiao. 2014. Reachability queries on large dynamic graphs: a total order approach. In SIGMOD. 1323--1334."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3529337.3529348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T15:03:29Z","timestamp":1727449409000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3529337.3529348"}},"subtitle":["efficient indexing for label-constrained reachability queries on large dynamic graphs"],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":33,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.14778\/3529337.3529348"],"URL":"https:\/\/doi.org\/10.14778\/3529337.3529348","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}