{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:11:39Z","timestamp":1779174699534,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T00:00:00Z","timestamp":1637625600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T00:00:00Z","timestamp":1637625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["FT170100128"],"award-info":[{"award-number":["FT170100128"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP210101393"],"award-info":[{"award-number":["DP210101393"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the National Science Foundation of China","award":["62102287"],"award-info":[{"award-number":["62102287"]}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP180103096"],"award-info":[{"award-number":["DP180103096"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP200101116"],"award-info":[{"award-number":["DP200101116"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s00778-021-00715-z","type":"journal-article","created":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T14:02:45Z","timestamp":1637676165000},"page":"629-647","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Span-reachability querying in large temporal graphs"],"prefix":"10.1007","volume":"31","author":[{"given":"Dong","family":"Wen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bohua","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5877-7387","authenticated-orcid":false,"given":"Dawei","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,23]]},"reference":[{"key":"715_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In: ESA, pages 24\u201335, (2012)","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"715_CR2","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/66926.66950","volume":"18","author":"R Agrawal","year":"1989","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. SIGMOD 18, 253\u2013262 (1989)","journal-title":"SIGMOD"},{"key":"715_CR3","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: SIGMOD, pages 349\u2013360, (2013)","DOI":"10.1145\/2463676.2465315"},{"key":"715_CR4","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: Chung, C., Broder, A.Z., Shim, K., Suel, T. (eds.) WWW, pp. 237\u2013248. ACM (2014)","DOI":"10.1145\/2566486.2568007"},{"key":"715_CR5","doi-asserted-by":"crossref","unstructured":"Anyanwu, K., Sheth, A.: $$\\rho $$-queries: enabling querying for semantic associations on the semantic web. In: WWW, pages 690\u2013699, (2003)","DOI":"10.1145\/775152.775249"},{"issue":"3","key":"715_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00873ED1V01Y201808DTM051","volume":"10","author":"A Bonifati","year":"2018","unstructured":"Bonifati, A., Fletcher, G., Voigt, H., Yakovets, N.: Querying graphs. Synth. Lect. Data Manag. 10(3), 1\u2013184 (2018)","journal-title":"Synth. Lect. Data Manag."},{"key":"715_CR7","doi-asserted-by":"crossref","unstructured":"Bramandia, R., Choi, B., Ng, W.K.: On incremental maintenance of 2-hop labeling of graphs. In: WWW, pages 845\u2013854, (2008)","DOI":"10.1145\/1367497.1367611"},{"issue":"5","key":"715_CR8","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/17445760.2012.668546","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emerg. Distrib. Syst. 27(5), 387\u2013408 (2012)","journal-title":"Int. J. Parallel Emerg. Distrib. Syst."},{"key":"715_CR9","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: An efficient algorithm for answering graph reachability queries. In: ICDE, pages 893\u2013902, (2008)","DOI":"10.1109\/ICDE.2008.4497498"},{"issue":"2\u20133","key":"715_CR10","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0166-218X(02)00497-3","volume":"128","author":"E Cheng","year":"2003","unstructured":"Cheng, E., Grossman, J.W., Lipman, M.J.: Time-stamped graphs and their associated influence digraphs. Discrete Appl. Math. 128(2\u20133), 317\u2013335 (2003)","journal-title":"Discrete Appl. Math."},{"key":"715_CR11","doi-asserted-by":"crossref","unstructured":"Cheng, J., Huang, S., Wu, H., Fu, A.W.-C.: Tf-label: a topological-folding labeling scheme for reachability querying in a large graph. In: SIGMOD, pages 193\u2013204, (2013)","DOI":"10.1145\/2463676.2465286"},{"issue":"3","key":"715_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Operations Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Operations Res."},{"issue":"5","key":"715_CR13","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. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"key":"715_CR14","unstructured":"Ferreira, A.: On models and algorithms for dynamic communication networks: The case for evolving graphs. In: In Proc. ALGOTEL, (2002)"},{"key":"715_CR15","doi-asserted-by":"publisher","first-page":"3453","DOI":"10.1109\/TKDE.2020.2968901","volume":"33","author":"Y Gao","year":"2020","unstructured":"Gao, Y., Zhang, T., Qiu, L., Linghu, Q., Chen, G.: Time-respecting flow graph pattern matching on temporal graphs. IEEE Trans. Knowl. Data Eng. 33, 3453\u20133467 (2020)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"715_CR16","doi-asserted-by":"crossref","unstructured":"Gurukar, S., Ranu, S., Ravindran, B.: Commit: A scalable approach to mining communication motifs from dynamic networks. In: SIGMOD, pages 475\u2013489, (2015)","DOI":"10.1145\/2723372.2737791"},{"issue":"2","key":"715_CR17","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.socnet.2004.01.007","volume":"26","author":"P Holme","year":"2004","unstructured":"Holme, P., Edling, C.R., Liljeros, F.: Structure and time evolution of an internet dating community. Soc. Netw. 26(2), 155\u2013174 (2004)","journal-title":"Soc. Netw."},{"issue":"3","key":"715_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme, P., Saram\u00e4ki, J.: Temporal networks. Phys. Rep. 519(3), 97\u2013125 (2012)","journal-title":"Phys. Rep."},{"key":"715_CR19","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Fuhry, D.: 3-hop: a high-compression indexing scheme for reachability query. In: SIGMOD, pages 813\u2013826, (2009)","DOI":"10.1145\/1559845.1559930"},{"key":"715_CR20","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: SIGMOD, pages 595\u2013608, (2008)","DOI":"10.1145\/1376616.1376677"},{"issue":"4","key":"715_CR21","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820\u2013842 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"715_CR22","doi-asserted-by":"crossref","unstructured":"Li, R.-H., Su, J., Qin, L., Yu, J.X., Dai, Q.: Persistent community search in temporal networks. In: ICDE, pages 797\u2013808 (2018)","DOI":"10.1109\/ICDE.2018.00077"},{"issue":"4","key":"715_CR23","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","volume":"12","author":"O Michail","year":"2016","unstructured":"Michail, O.: An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12(4), 239\u2013280 (2016)","journal-title":"Internet Math."},{"key":"715_CR24","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Efficient creation and incremental maintenance of the hopi index for complex xml document collections. In: ICDE, pages 360\u2013371, (2005)"},{"key":"715_CR25","unstructured":"Semertzidis, K., Pitoura, E., Lillis, K.: Timereach: Historical reachability queries on evolving graphs. In: EDBT, pages 121\u2013132, (2015)"},{"key":"715_CR26","doi-asserted-by":"crossref","unstructured":"Sengupta, N., Bagchi, A., Ramanath, M., Bedathur, S.: Arrow: Approximating reachability using random walks over web-scale graphs. In: ICDE, pages 470\u2013481, (2019)","DOI":"10.1109\/ICDE.2019.00049"},{"issue":"3","key":"715_CR27","first-page":"683","volume":"29","author":"J Su","year":"2016","unstructured":"Su, J., Zhu, Q., Wei, H., Yu, J.X.: Reachability querying: can it be even faster? TKDE 29(3), 683\u2013697 (2016)","journal-title":"TKDE"},{"key":"715_CR28","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.tcs.2015.09.030","volume":"609","author":"T Viard","year":"2016","unstructured":"Viard, T., Latapy, M., Magnien, C.: Computing maximal cliques in link streams. Theor. Comput. Sci. 609, 245\u2013252 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"715_CR29","doi-asserted-by":"crossref","unstructured":"Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: Answering graph reachability queries in constant time. In: ICDE, page 75 (2006)","DOI":"10.1109\/ICDE.2006.53"},{"key":"715_CR30","doi-asserted-by":"crossref","unstructured":"Wang, S., Lin, W., Yang, Y., Xiao, X., Zhou, S.: Efficient route planning on public transportation networks: A labelling approach. In: SIGMOD, pages 967\u2013982, (2015)","DOI":"10.1145\/2723372.2749456"},{"issue":"12","key":"715_CR31","first-page":"1191","volume":"7","author":"H Wei","year":"2014","unstructured":"Wei, H., Yu, J.X., Lu, C., Jin, R.: Reachability querying: An independent permutation labeling approach. PVLDB 7(12), 1191\u20131202 (2014)","journal-title":"PVLDB"},{"key":"715_CR32","doi-asserted-by":"crossref","unstructured":"Wen, D., Huang, Y., Zhang, Y., Qin, L., Zhang, W., Lin, X.: Efficiently answering span-reachability queries in large temporal graphs. In: ICDE, pages 1153\u20131164. IEEE, (2020)","DOI":"10.1109\/ICDE48307.2020.00104"},{"key":"715_CR33","doi-asserted-by":"crossref","unstructured":"Wu, H., Huang, Y., Cheng, J., Li, J., Ke, Y.: Reachability and time-based path queries in temporal graphs. In: ICDE, pages 145\u2013156, (2016)","DOI":"10.1109\/ICDE.2016.7498236"},{"issue":"02","key":"715_CR34","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"BB Xuan","year":"2003","unstructured":"Xuan, B.B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(02), 267\u2013285 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"715_CR35","doi-asserted-by":"crossref","unstructured":"Yano, Y., Akiba, T., Iwata, Y., Yoshida, Y.: Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In: CIKM, pages 1601\u20131606, (2013)","DOI":"10.1145\/2505515.2505724"},{"issue":"4","key":"715_CR36","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00778-011-0256-4","volume":"21","author":"H Y\u0131ld\u0131r\u0131m","year":"2012","unstructured":"Y\u0131ld\u0131r\u0131m, H., Chaoji, V., Zaki, M.J.: Grail: a scalable index for reachability queries in very large graphs. VLDBJ 21(4), 509\u2013534 (2012)","journal-title":"VLDBJ"},{"key":"715_CR37","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":"715_CR38","doi-asserted-by":"crossref","unstructured":"Yu, J.X., Cheng, J.: Graph reachability queries: a survey. In: Managing and Mining Graph Data, pages 181\u2013215. (2010)","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"715_CR39","doi-asserted-by":"crossref","unstructured":"Zhang, T., Gao, Y., Chen, L., Guo, W., Pu, S., Zheng, B., Jensen, C.S.: Efficient distributed reachability querying of massive temporal graphs. VLDBJ, pages 1\u201326, (2019)","DOI":"10.1007\/s00778-019-00572-x"},{"key":"715_CR40","first-page":"406","volume":"11448","author":"T Zhang","year":"2019","unstructured":"Zhang, T., Gao, Y., Li, C., Ge, C., Guo, W., Zhou, Q.: Distributed reachability queries on massive graphs. DASFAA 11448, 406\u2013410 (2019)","journal-title":"DASFAA"},{"key":"715_CR41","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, pages 1323\u20131334, (2014)","DOI":"10.1145\/2588555.2612181"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00715-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00715-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00715-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T21:55:24Z","timestamp":1726178124000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00715-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,23]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["715"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00715-z","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,23]]},"assertion":[{"value":"25 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}