{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T15:21:29Z","timestamp":1771600889461,"version":"3.50.1"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030731960","type":"print"},{"value":"9783030731977","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-73197-7_52","type":"book-chapter","created":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T19:03:01Z","timestamp":1617735781000},"page":"761-777","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["DBL: Efficient Reachability Queries on Dynamic Graphs"],"prefix":"10.1007","author":[{"given":"Qiuyi","family":"Lyu","sequence":"first","affiliation":[]},{"given":"Yuchen","family":"Li","sequence":"additional","affiliation":[]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[]},{"given":"Bin","family":"Gong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,6]]},"reference":[{"key":"52_CR1","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 349\u2013360. ACM (2013)","DOI":"10.1145\/2463676.2465315"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling. In: Proceedings of the 23rd International Conference on World Wide Web, pp. 237\u2013248 (2014)","DOI":"10.1145\/2566486.2568007"},{"issue":"4\u20135","key":"52_CR3","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.physrep.2005.10.009","volume":"424","author":"S Boccaletti","year":"2006","unstructured":"Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.U.: Complex networks: structure and dynamics. Phys. Rep. 424(4\u20135), 175\u2013308 (2006)","journal-title":"Phys. Rep."},{"issue":"5","key":"52_CR4","first-page":"682","volume":"22","author":"R Bramandia","year":"2010","unstructured":"Bramandia, R., Choi, B., Ng, W.K.: Incremental maintenance of 2-hop labeling of large graphs. TKDE 22(5), 682\u2013698 (2010)","journal-title":"TKDE"},{"issue":"5","key":"52_CR5","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SICOMP 32(5), 1338\u20131355 (2003)","journal-title":"SICOMP"},{"issue":"1","key":"52_CR6","first-page":"93","volume":"11","author":"W Guo","year":"2017","unstructured":"Guo, W., Li, Y., Sha, M., Tan, K.L.: Parallel personalized pagerank on dynamic graphs. PVLDB 11(1), 93\u2013106 (2017)","journal-title":"PVLDB"},{"key":"52_CR7","unstructured":"Henzinger, M.R., King, V.: Fully dynamic biconnectivity and transitive closure. In: FOCS, pp. 664\u2013672. IEEE (1995)"},{"issue":"1","key":"52_CR8","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/1929934.1929941","volume":"36","author":"R Jin","year":"2011","unstructured":"Jin, R., Ruan, N., Xiang, Y., Wang, H.: Path-tree: an efficient reachability indexing scheme for large directed graphs. TODS 36(1), 7 (2011)","journal-title":"TODS"},{"key":"52_CR9","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection (June 2014). http:\/\/snap.stanford.edu\/data"},{"key":"52_CR10","doi-asserted-by":"crossref","unstructured":"Li, Y., Zhu, Q., Lyu, Z., Huang, Z., Sun, J.: Dycuckoo: dynamic hash tables on gpus. In: ICDE (2021)","DOI":"10.1109\/ICDE51399.2021.00070"},{"key":"52_CR11","doi-asserted-by":"crossref","unstructured":"Lyu, Q., Li, Y., He, B., Gong, B.: DBL: Efficient reachability queries on dynamic graphs (complete version) (2021)","DOI":"10.1007\/978-3-030-73197-7_52"},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"Potamias, M., Bonchi, F., Castillo, C., Gionis, A.: Fast shortest path distance estimation in large networks. In: CIKM, pp. 867\u2013876. ACM (2009)","DOI":"10.1145\/1645953.1646063"},{"key":"52_CR13","doi-asserted-by":"publisher","unstructured":"Qiu, X., et al.: Real-time constrained cycle detection in large dynamic graphs. In: Proceedings of the VLDB Endowment, vol. 11, pp. 1876\u20131888 (08 2018). https:\/\/doi.org\/10.14778\/3229863.3229874","DOI":"10.14778\/3229863.3229874"},{"key":"52_CR14","doi-asserted-by":"crossref","unstructured":"Roditty, L.: Decremental maintenance of strongly connected components. In: SODA, pp. 1143\u20131150. SIAM (2013)","DOI":"10.1137\/1.9781611973105.82"},{"issue":"3","key":"52_CR15","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1137\/13093618X","volume":"45","author":"L Roditty","year":"2016","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. SICOMP 45(3), 712\u2013733 (2016)","journal-title":"SICOMP"},{"key":"52_CR16","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Efficient creation and incremental maintenance of the HOPI index for complex xml document collections. In: ICDE, pp. 360\u2013371. IEEE (2005)"},{"key":"52_CR17","doi-asserted-by":"crossref","unstructured":"Seufert, S., Anand, A., Bedathur, S., Weikum, G.: Ferrari: Flexible and efficient reachability range assignment for graph indexing. In: ICDE, pp. 1009\u20131020. IEEE (2013)","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"52_CR18","doi-asserted-by":"crossref","unstructured":"Sha, M., Li, Y., He, B., Tan, K.L.: Accelerating dynamic graph analytics on GPUs. PVLDB 11(1), (2017)","DOI":"10.14778\/3151113.3151122"},{"key":"52_CR19","unstructured":"Su, J., Zhu, Q., Wei, H., Yu, J.X.: Reachability querying: can it be even faster? TKDE 1, 1 (2017)"},{"key":"52_CR20","doi-asserted-by":"crossref","unstructured":"Valstar, L.D., Fletcher, G.H., Yoshida, Y.: Landmark indexing for evaluation of label-constrained reachability queries. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 345\u2013358 (2017)","DOI":"10.1145\/3035918.3035955"},{"key":"52_CR21","unstructured":"Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: answering graph reachability queries in constant time. In: ICDE, p. 75. IEEE (2006)"},{"issue":"7","key":"52_CR22","doi-asserted-by":"publisher","first-page":"805","DOI":"10.14778\/3067421.3067429","volume":"10","author":"Y Wang","year":"2017","unstructured":"Wang, Y., Fan, Q., Li, Y., Tan, K.L.: Real-time influence maximization on dynamic social streams. Proc. VLDB Endowment 10(7), 805\u2013816 (2017)","journal-title":"Proc. VLDB Endowment"},{"issue":"1","key":"52_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00778-017-0468-3","volume":"27","author":"H Wei","year":"2017","unstructured":"Wei, H., Yu, J.X., Lu, C., Jin, R.: Reachability querying: an independent permutation labeling approach. VLDB J. 27(1), 1\u201326 (2017). https:\/\/doi.org\/10.1007\/s00778-017-0468-3","journal-title":"VLDB J."},{"issue":"1\u20132","key":"52_CR24","first-page":"276","volume":"3","author":"H Yildirim","year":"2010","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: Grail: scalable reachability index for large graphs. PVLDB 3(1\u20132), 276\u2013284 (2010)","journal-title":"PVLDB"},{"key":"52_CR25","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: Dagger: a scalable index for reachability queries in large dynamic graphs. arXiv preprint arXiv:1301.0977 (2013)"},{"key":"52_CR26","doi-asserted-by":"crossref","unstructured":"Zhu, A.D., Lin, W., Wang, S., Xiao, X.: Reachability queries on large dynamic graphs: a total order approach. In: SIGMOD, pp. 1323\u20131334. ACM (2014)","DOI":"10.1145\/2588555.2612181"}],"updated-by":[{"DOI":"10.1007\/978-3-030-73197-7_54","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,4,6]],"date-time":"2021-04-06T00:00:00Z","timestamp":1617667200000}}],"container-title":["Lecture Notes in Computer Science","Database Systems for Advanced Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-73197-7_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,7]],"date-time":"2021-08-07T15:21:20Z","timestamp":1628349680000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-73197-7_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030731960","9783030731977"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-73197-7_52","relation":{"correction":[{"id-type":"doi","id":"10.1007\/978-3-030-73197-7_54","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"6 April 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"6 April 2021","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The original version of the book was inadvertently published with incorrect acknowledgements in chapters 28 and 31. The acknowledgements have been corrected and read as follows: Acknowledgement: \u201cThis paper is supported by the National Key Research and Development Program of China (Grant No. 2018YFB1403400), the National Natural Science Foundation of China (Grant No. 61876080), the Key Research and Development Program of Jiangsu (Grant No. BE2019105), the Collaborative Innovation Center of Novel Software Technology and Industrialization at Nanjing University.\u201d","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"In chapter 52, the original version of this chapter affiliation of second author has been corrected and on page 775 the citation of Figure 6 was inadvertently published as \u201cTable 6\u201d. This has been corrected.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DASFAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Database Systems for Advanced Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taipei","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dasfaa2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/dm.iis.sinica.edu.tw\/DASFAA2021\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"CMT","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"490","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"98","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the Corona pandemic this event was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}