{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T23:37:52Z","timestamp":1722987472472},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T00:00:00Z","timestamp":1693785600000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2023,9]]},"abstract":"Abstract<\/jats:title>In the real world, road networks with weight and label on edges can be applied in several application domains. The shortest path query with label restrictions has been receiving increasing attention recently. To efficiently answer such kind of queries, a novel index, namely Contraction Hierarchies with Label Restrictions (CHLR), is proposed in the literature. However, existing studies mainly focus on the static road networks and do not support the CHLR maintenance when the road networks are dynamically changed. Motivated by this, in this paper, we investigate the CHLR maintenance problem in dynamic road networks. We first devise a baseline approach to update CHLR by recomputing the potential affected shortcuts. However, many shortcuts recomputed in baseline do not change in fact, which leads to unnecessary overhead of the baseline. To overcome the drawbacks of baseline, we further propose a novel CHLR maintenance algorithm which can only travel little shortcuts through an update propagate chain with accuracy guarantee. Moreover, an optimization strategy is presented to further improve the efficiency of index maintenance. Considering the frequency of edge changes, we also propose a batch index maintenance algorithm to handle batch edge changes which can process a large number of edge changes at once. Furthermore, a parallel method is proposed to further accelerate calculations. Extensive and comprehensive experiments are conducted on real road networks. The experimental results demonstrate the efficiency and effectiveness of our proposed algorithms.<\/jats:p>","DOI":"10.1007\/s41019-023-00227-6","type":"journal-article","created":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T05:01:29Z","timestamp":1693803689000},"page":"263-278","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fully Dynamic Contraction Hierarchies with Label Restrictions on Road Networks"],"prefix":"10.1007","volume":"8","author":[{"given":"Zi","family":"Chen","sequence":"first","affiliation":[]},{"given":"Bo","family":"Feng","sequence":"additional","affiliation":[]},{"given":"Long","family":"Yuan","sequence":"additional","affiliation":[]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[]},{"given":"Liping","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,4]]},"reference":[{"key":"227_CR1","doi-asserted-by":"crossref","unstructured":"Abraham I, Delling D, Goldberg AV, Werneck RFF (2011) A hub-based labeling algorithm for shortest paths in road networks. In: Proceedings of SEA vol 6630, pp 230\u2013241","DOI":"10.1007\/978-3-642-20662-7_20"},{"key":"227_CR2","doi-asserted-by":"crossref","unstructured":"Akiba T, Iwata Y, and Yoshida Y (2013) Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: SIGMOD 349\u2013360","DOI":"10.1145\/2463676.2465315"},{"issue":"1","key":"227_CR3","first-page":"151","volume":"25","author":"S Anirban","year":"2022","unstructured":"Anirban S, Wang J, Islam MS, Kayesh H, Li J, Huang ML (2022) Compression techniques for 2-hop labeling for shortest distance queries. WWW 25(1):151\u2013174","journal-title":"WWW"},{"issue":"1","key":"227_CR4","first-page":"2.4:1","volume":"24","author":"V Buchhold","year":"2019","unstructured":"Buchhold V, Sanders P, Wagner D (2019) Real-time traffic assignment using engineered customizable contraction hierarchies. ACM J. Exp. Algorithmics 24(1):2.4:1-2.4:28","journal-title":"ACM J. Exp. Algorithmics"},{"key":"227_CR5","unstructured":"Chen Y, Perera L, Thompson RG (2018) An advanced method to provide best route information in city logistics with toll roads. In: ATRF"},{"key":"227_CR6","doi-asserted-by":"crossref","unstructured":"Chen Z, Fu AW, Jiang M, Lo E, and Zhang P (2021) P2H: efficient distance querying on road networks by projected vertex separators. In: SIGMOD, pp 313\u2013325. ACM","DOI":"10.1145\/3448016.3459245"},{"key":"227_CR7","unstructured":"Chen Z, Yuan L, Han L, Qian Z (2021) Higher-order truss decomposition in graphs. In: IEEE TKDE, pp 1\u20131"},{"key":"227_CR8","doi-asserted-by":"crossref","unstructured":"Chen Z, Yuan L, Lin X, Qin L, Yang J (2020) Efficient maximal balanced clique enumeration in signed networks. In: WWW, pp 339\u2013349. ACM\/IW3C2","DOI":"10.1145\/3366423.3380119"},{"key":"227_CR9","doi-asserted-by":"crossref","unstructured":"Chen Z, Zhao Y, Yuan L, Lin X, Wang K (2023) Index-based biclique percolation communities search on bipartite graphs. In: ICDE, pp 2699\u20132712","DOI":"10.1109\/ICDE55515.2023.00207"},{"key":"227_CR10","unstructured":"Dean B (2022) Uber statistics 2022: how many people ride with uber? https:\/\/backlinko.com\/uber-users"},{"issue":"1","key":"227_CR11","first-page":"1.5:1","volume":"21","author":"J Dibbelt","year":"2016","unstructured":"Dibbelt J, Strasser B, Wagner D (2016) Customizable contraction hierarchies. ACM J. Exp. Algorithmics 21(1):1.5:1-1.5:49","journal-title":"ACM J. Exp. Algorithmics"},{"key":"227_CR12","unstructured":"Didi (2022) Didi statistics and facts. https:\/\/expandedramblings.com\/index.php\/didi-chuxing-facts-statistics\/"},{"key":"227_CR13","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269\u2013271","journal-title":"Numer Math"},{"key":"227_CR14","first-page":"1443","volume":"14","author":"R Engstr\u00f6m","year":"2016","unstructured":"Engstr\u00f6m R (2016) The roads\u2019 role in the freight transport system. Transp Res Proc 14:1443\u20131452","journal-title":"Transp Res Proc"},{"key":"227_CR15","doi-asserted-by":"crossref","unstructured":"Feng B, Chen Z, Yuan L, Lin X, Wang L (2023) Contraction hierarchies with label restrictions maintenance in dynamic road networks. In: Database systems for advanced applications, pp 269\u2013285","DOI":"10.1007\/978-3-031-30675-4_18"},{"key":"227_CR16","doi-asserted-by":"crossref","unstructured":"Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Proceedings of WEA, vol 5038, pp 319\u2013333","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"227_CR17","doi-asserted-by":"crossref","unstructured":"Hassan MS, Aref WG, Aly AM (2016) Graph indexing for shortest-path finding over dynamic sub-graphs. In: SIGMOD, pp 1183\u20131197. ACM","DOI":"10.1145\/2882903.2882933"},{"issue":"4","key":"227_CR18","doi-asserted-by":"publisher","first-page":"492","DOI":"10.14778\/3372716.3372722","volume":"13","author":"K Lakhotia","year":"2019","unstructured":"Lakhotia K, Kannan R, Dong Q, Prasanna VK (2019) Planting trees for scalable and efficient canonical hub labeling. Proc VLDB Endow 13(4):492\u2013505","journal-title":"Proc VLDB Endow"},{"key":"227_CR19","doi-asserted-by":"crossref","unstructured":"Li W, Qiao M, Qin L, Zhang Y, Chang L, Lin X (2019) Scaling distance labeling on small-world networks. In: SIGMOD, pp 1060\u20131077","DOI":"10.1145\/3299869.3319877"},{"issue":"4","key":"227_CR20","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1145\/3186728.3164141","volume":"11","author":"Y Li","year":"2017","unstructured":"Li Y, U LH, Yiu ML, Kou NM (2017) An experimental study on hub labeling based shortest path algorithms. Proc VLDB Endow 11(4):445\u2013457","journal-title":"Proc VLDB Endow"},{"key":"227_CR21","doi-asserted-by":"crossref","unstructured":"Liu B, Yuan L, Lin X, Qin L, Zhang W, Zhou J (2019) Efficient ($$\\alpha$$, $$\\beta$$)-core computation: an index-based approach. In: WWW, pp 1130\u20131141. ACM","DOI":"10.1145\/3308558.3313522"},{"key":"227_CR22","unstructured":"Mahajan B Classification of roads in india. https:\/\/civiconcepts.com\/blog\/classification-of-roads"},{"issue":"2","key":"227_CR23","first-page":"191","volume":"1","author":"JL Mwakalonge","year":"2012","unstructured":"Mwakalonge JL, Moses R (2012) Evaluation of truck lane restriction on non-limited access urban arterials. IJTST 1(2):191\u2013204","journal-title":"IJTST"},{"key":"227_CR24","doi-asserted-by":"crossref","unstructured":"Ouyang D, Qin L, Chang L, Lin X, Zhang Y, Zhu Q (2018) When hierarchy meets 2-hop-labeling: efficient shortest distance queries on road networks. In: SIGMOD, pp 709\u2013724","DOI":"10.1145\/3183713.3196913"},{"issue":"5","key":"227_CR25","doi-asserted-by":"publisher","first-page":"602","DOI":"10.14778\/3377369.3377371","volume":"13","author":"D Ouyang","year":"2020","unstructured":"Ouyang D, Yuan L, Qin L, Chang L, Zhang Y, Lin X (2020) Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees. Proc VLDB Endow 13(5):602\u2013615","journal-title":"Proc VLDB Endow"},{"key":"227_CR26","doi-asserted-by":"crossref","unstructured":"Peng Y, Yu JX, Wang S (2023) PSPC: efficient parallel shortest path counting on large-scale graphs. In: ICDE, pp 896\u2013908. IEEE","DOI":"10.1109\/ICDE55515.2023.00074"},{"issue":"2","key":"227_CR27","doi-asserted-by":"publisher","first-page":"69","DOI":"10.14778\/1921071.1921074","volume":"4","author":"MN Rice","year":"2010","unstructured":"Rice MN, Tsotras VJ (2010) Graph indexing of road networks for shortest path queries with label restrictions. Proc VLDB Endow 4(2):69\u201380","journal-title":"Proc VLDB Endow"},{"key":"227_CR28","unstructured":"Transportation (2023) Urban public transportation in china-statistics facts. https:\/\/www.statista.com\/topics\/5662\/urban-public-transportation-in-china\/"},{"key":"227_CR29","doi-asserted-by":"crossref","unstructured":"Wang Y, Wang Q, Koehler H, Lin Y (2021) Query-by-sketch: scaling shortest path graph queries on very large networks. In: SIGMOD, pp 1946\u20131958. ACM","DOI":"10.1145\/3448016.3452826"},{"key":"227_CR30","doi-asserted-by":"crossref","unstructured":"Wang Y, Yuan L, Chen Z, Zhang W, Lin X, Liu Q (2023) Towards efficient shortest path counting on billion-scale graphs. In: ICDE, pp 2579\u20132592. IEEE","DOI":"10.1109\/ICDE55515.2023.00198"},{"issue":"5","key":"227_CR31","doi-asserted-by":"publisher","first-page":"406","DOI":"10.14778\/2140436.2140438","volume":"5","author":"L Wu","year":"2012","unstructured":"Wu L, Xiao X, Deng D, Cong G, Zhu AD, Zhou S (2012) Shortest path and distance queries on road networks: an experimental evaluation. Proc VLDB Endow 5(5):406\u2013417","journal-title":"Proc VLDB Endow"},{"issue":"5","key":"227_CR32","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1109\/TKDE.2017.2783933","volume":"30","author":"L Yuan","year":"2018","unstructured":"Yuan L, Qin L, Zhang W, Chang L, Yang J (2018) Index-based densest clique percolation community search in networks. IEEE Trans Knowl Data Eng 30(5):922\u2013935","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"10","key":"227_CR33","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.14778\/3339490.3339491","volume":"12","author":"Y Yuan","year":"2019","unstructured":"Yuan Y, Lian X, Wang G, Ma Y, Wang Y (2019) Constrained shortest path query in a large time-dependent graph. Proc VLDB Endow 12(10):1058\u20131070","journal-title":"Proc VLDB Endow"},{"issue":"11","key":"227_CR34","doi-asserted-by":"publisher","first-page":"2640","DOI":"10.14778\/3551793.3551820","volume":"15","author":"J Zhang","year":"2022","unstructured":"Zhang J, Li W, Yuan L, Qin L, Zhang Y, Chang L (2022) Shortest-path queries on complex networks: experiments, analyses, and improvement. Proc VLDB Endow 15(11):2640\u20132652","journal-title":"Proc VLDB Endow"},{"issue":"3","key":"227_CR35","doi-asserted-by":"publisher","first-page":"686","DOI":"10.14778\/3494124.3494148","volume":"15","author":"J Zhang","year":"2021","unstructured":"Zhang J, Yuan L, Li W, Qin L, Zhang Y (2021) Efficient label-constrained shortest path queries on road networks: a tree decomposition approach. Proc VLDB Endow 15(3):686\u2013698","journal-title":"Proc VLDB Endow"},{"key":"227_CR36","doi-asserted-by":"crossref","unstructured":"Zhang M, Li L, Hua W, Mao R, Chao P, Zhou X (2021) Dynamic hub labeling for road networks. In: ICDE, pp 336\u2013347","DOI":"10.1109\/ICDE51399.2021.00036"},{"key":"227_CR37","doi-asserted-by":"crossref","unstructured":"Zhang Y, Yu JX (2022) Relative subboundedness of contraction hierarchy and hierarchical 2-hop index in dynamic road networks. In: SIGMOD, pp 1992\u20132005","DOI":"10.1145\/3514221.3517875"},{"key":"227_CR38","doi-asserted-by":"crossref","unstructured":"Zhao Y, Chen Z, Chen C, Wang X, Lin X, Zhang W (2022) Finding the maximum $$k$$-balanced biclique on weighted bipartite graphs. In: IEEE TKDE, pp 1\u201314","DOI":"10.1109\/TKDE.2022.3206351"},{"key":"227_CR39","doi-asserted-by":"crossref","unstructured":"Zhu AD, Ma H, Xiao X, Luo S, Tang Y, Zhou S (2013) Shortest path and distance queries on road networks: towards bridging theory and practice. In: SIGMOD, pp 857\u2013868","DOI":"10.1145\/2463676.2465277"},{"key":"227_CR40","doi-asserted-by":"crossref","unstructured":"Zhu AD, Xiao X, Wang S, Lin W (2013) Efficient single-source shortest path and distance queries on large graphs. In: SIGKDD, pp 998\u20131006. ACM","DOI":"10.1145\/2487575.2487665"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-023-00227-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-023-00227-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-023-00227-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T09:04:42Z","timestamp":1695114282000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-023-00227-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["227"],"URL":"https:\/\/doi.org\/10.1007\/s41019-023-00227-6","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9]]},"assertion":[{"value":"17 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}