{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:12:41Z","timestamp":1780765961132,"version":"3.54.1"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T00:00:00Z","timestamp":1569628800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T00:00:00Z","timestamp":1569628800000},"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":["The VLDB Journal"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s00778-019-00572-x","type":"journal-article","created":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T11:03:17Z","timestamp":1569668597000},"page":"871-896","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Efficient distributed reachability querying of massive temporal graphs"],"prefix":"10.1007","volume":"28","author":[{"given":"Tianming","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Guo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shiliang","family":"Pu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baihua","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,9,28]]},"reference":[{"key":"572_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: SIGMOD, pp. 253\u2013262 (1989)","DOI":"10.1145\/66926.66950"},{"issue":"3","key":"572_CR2","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1007\/s10586-015-0472-6","volume":"18","author":"O Batarfi","year":"2015","unstructured":"Batarfi, O., Shawi, R.E., Fayoumi, A.G., Nouri, R., Beheshti, S., Barnawi, A., Sakr, S.: Large scale graph processing systems: survey and an experimental evaluation. Clust. Comput. 18(3), 1189\u20131213 (2015)","journal-title":"Clust. Comput."},{"issue":"5","key":"572_CR3","first-page":"387","volume":"27","author":"A Casteigts","year":"2012","unstructured":"Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. IJPEDS 27(5), 387\u2013408 (2012)","journal-title":"IJPEDS"},{"key":"572_CR4","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on dags. In: VLDB, pp. 493\u2013504 (2005)"},{"key":"572_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: An efficient algorithm for answering graph reachability queries. In: ICDE, pp. 893\u2013902 (2008)","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"572_CR6","doi-asserted-by":"crossref","unstructured":"Cheng, J., Huang, S., Wu, H., Fu, A.W.: Tf-label: A topological-folding labeling scheme for reachability querying in a large graph. In: SIGMOD, pp. 193\u2013204 (2013)","DOI":"10.1145\/2463676.2465286"},{"issue":"1","key":"572_CR7","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: Mapreduce: Simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"issue":"11","key":"572_CR8","first-page":"1304","volume":"5","author":"W Fan","year":"2012","unstructured":"Fan, W., Wang, X., Wu, Y.: Performance guarantees for distributed reachability queries. PVLDB 5(11), 1304\u20131315 (2012)","journal-title":"PVLDB"},{"issue":"4","key":"572_CR9","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/s00778-017-0460-y","volume":"26","author":"Y Gao","year":"2017","unstructured":"Gao, Y., Miao, X., Chen, G., Zheng, B., Cai, D., Cui, H.: On efficiently finding reverse k-nearest neighbors over uncertain graphs. VLDB J. 26(4), 467\u2013492 (2017)","journal-title":"VLDB J."},{"key":"572_CR10","unstructured":"Gonzalez, J.E., Xin, R.S., Dave, A., Crankshaw, D., Franklin, M.J., Stoica, I.: Graphx: Graph processing in a distributed dataflow framework. In: OSDI, pp. 599\u2013613 (2014)"},{"key":"572_CR11","doi-asserted-by":"crossref","unstructured":"Gurajada, S., Theobald, M.: Distributed set reachability. In: SIGMOD, pp. 1247\u20131261 (2016)","DOI":"10.1145\/2882903.2915226"},{"issue":"3","key":"572_CR12","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":"572_CR13","unstructured":"Huang, S., Cheng, J., Wu, H.: Temporal graph traversals: definitions, algorithms, and applications. CoRR arxiv:1401.1919 (2014)"},{"key":"572_CR14","doi-asserted-by":"crossref","unstructured":"Huang, S., Fu, A.W., Liu, R.: Minimum spanning trees in temporal graphs. In: SIGMOD, pp. 419\u2013430 (2015)","DOI":"10.1145\/2723372.2723717"},{"issue":"4","key":"572_CR15","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/99935.99944","volume":"15","author":"HV Jagadish","year":"1990","unstructured":"Jagadish, H.V.: A compression technique to materialize transitive closure. ACM Trans. Database Syst. 15(4), 558\u2013598 (1990)","journal-title":"ACM Trans. Database Syst."},{"key":"572_CR16","doi-asserted-by":"crossref","unstructured":"Jin, R., Ruan, N., Dey, S., Yu, J.X.: SCARAB: scaling reachability computation on large graphs. In: SIGMOD, pp. 169\u2013180 (2012)","DOI":"10.1145\/2213836.2213856"},{"issue":"1","key":"572_CR17","doi-asserted-by":"publisher","first-page":"7:1","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. ACM Trans. Database Syst. 36(1), 7:1\u20137:44 (2011)","journal-title":"ACM Trans. Database Syst."},{"issue":"14","key":"572_CR18","first-page":"1978","volume":"6","author":"R Jin","year":"2013","unstructured":"Jin, R., Wang, G.: Simple, fast, and scalable reachability oracle. PVLDB 6(14), 1978\u20131989 (2013)","journal-title":"PVLDB"},{"key":"572_CR19","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: SIGMOD, pp. 595\u2013608 (2008)","DOI":"10.1145\/1376616.1376677"},{"issue":"6","key":"572_CR20","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1016\/j.physa.2008.11.021","volume":"388","author":"V Kostakos","year":"2009","unstructured":"Kostakos, V.: Temporal graphs. Phys. A Stat. Mech. Appl. 388(6), 1007\u20131023 (2009)","journal-title":"Phys. A Stat. Mech. Appl."},{"key":"572_CR21","doi-asserted-by":"crossref","unstructured":"Koubarakis, M., Stamou, G.B., Stoilos, G., Horrocks, I., Kolaitis, P.G., Lausen, G., Weikum, G. (eds.): Reasoning Web. Reasoning on the Web in the Big Data Era. Lecture Notes in Computer Science, vol. 8714. Springer (2014)","DOI":"10.1007\/978-3-319-10587-1"},{"issue":"8","key":"572_CR22","first-page":"716","volume":"5","author":"Y Low","year":"2012","unstructured":"Low, Y., Gonzalez, J., Kyrola, A., Bickson, D., Guestrin, C., Hellerstein, J.M.: Distributed graphlab: a framework for machine learning in the cloud. PVLDB 5(8), 716\u2013727 (2012)","journal-title":"PVLDB"},{"key":"572_CR23","doi-asserted-by":"crossref","unstructured":"Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: A system for large-scale graph processing. In: SIGMOD, pp. 135\u2013146 (2010)","DOI":"10.1145\/1807167.1807184"},{"key":"572_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.006","volume":"634","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 634, 1\u201323 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"572_CR25","doi-asserted-by":"crossref","unstructured":"Nicosia, V., Tang, J.K., Musolesi, M., Russo, G., Mascolo, C., Latora, V.: Components in time-varying graphs. CoRR arxiv:1106.2134 (2011)","DOI":"10.1063\/1.3697996"},{"key":"572_CR26","doi-asserted-by":"crossref","unstructured":"Pan, R.K., Saram\u00e4ki, J.: Path lengths, correlations, and centrality in temporal networks. CoRR arxiv:1101.5913 (2011)","DOI":"10.1103\/PhysRevE.84.016105"},{"key":"572_CR27","doi-asserted-by":"crossref","unstructured":"Redmond, U., Cunningham, P.: Temporal subgraph isomorphism. In: ASONAM, pp. 1451\u20131452 (2013)","DOI":"10.1145\/2492517.2492586"},{"key":"572_CR28","unstructured":"Redmond, U., Cunningham, P.: Subgraph isomorphism in temporal networks. CoRR arxiv:1605.02174 (2016)"},{"key":"572_CR29","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., de\u00a0Moor, O.: A memory efficient reachability data structure through bit vector compression. In: SIGMOD, pp. 913\u2013924 (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"572_CR30","doi-asserted-by":"crossref","unstructured":"Seufert, S., Anand, A., Bedathur, S.J., Weikum, G.: FERRARI: flexible and efficient reachability range assignment for graph indexing. In: ICDE, pp. 1009\u20131020 (2013)","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"572_CR31","doi-asserted-by":"crossref","unstructured":"Shao, B., Wang, H., Li, Y.: Trinity: A distributed graph engine on a memory cloud. In: SIGMOD, pp. 505\u2013516 (2013)","DOI":"10.1145\/2463676.2467799"},{"issue":"3","key":"572_CR32","first-page":"683","volume":"29","author":"J Su","year":"2017","unstructured":"Su, J., Zhu, Q., Wei, H., Yu, J.X.: Reachability querying: can it be even faster? TKDE 29(3), 683\u2013697 (2017)","journal-title":"TKDE"},{"issue":"3","key":"572_CR33","first-page":"193","volume":"7","author":"Y Tian","year":"2013","unstructured":"Tian, Y., Balmin, A., Corsten, S.A., Tatikonda, S., McPherson, J.: From think like a vertex to think like a graph. PVLDB 7(3), 193\u2013204 (2013)","journal-title":"PVLDB"},{"key":"572_CR34","doi-asserted-by":"crossref","unstructured":"Tri\u00dfl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: SIGMOD, pp. 845\u2013856 (2007)","DOI":"10.1145\/1247480.1247573"},{"issue":"1","key":"572_CR35","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s41019-016-0024-y","volume":"2","author":"K Ueno","year":"2017","unstructured":"Ueno, K., Suzumura, T., Maruyama, N., Fujisawa, K., Matsuoka, S.: Efficient breadth-first search on massively parallel and distributed-memory machines. Data Sci. Eng. 2(1), 22\u201335 (2017)","journal-title":"Data Sci. Eng."},{"key":"572_CR36","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.\u00a075 (2006)"},{"key":"572_CR37","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, pp. 967\u2013982 (2015)","DOI":"10.1145\/2723372.2749456"},{"issue":"12","key":"572_CR38","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"},{"issue":"9","key":"572_CR39","first-page":"721","volume":"7","author":"H Wu","year":"2014","unstructured":"Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. PVLDB 7(9), 721\u2013732 (2014)","journal-title":"PVLDB"},{"key":"572_CR40","doi-asserted-by":"crossref","unstructured":"Wu, H., Huang, Y., Cheng, J., Li, J., Ke, Y.: Efficient processing of reachability and time-based path queries in a temporal graph. CoRR arxiv:1601.05909 (2016)","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"572_CR41","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, pp. 145\u2013156 (2016)","DOI":"10.1109\/ICDE.2016.7498236"},{"issue":"14","key":"572_CR42","first-page":"1981","volume":"7","author":"D Yan","year":"2014","unstructured":"Yan, D., Cheng, J., Lu, Y., Ng, W.: Blogel: a block-centric framework for distributed computation on real-world graphs. PVLDB 7(14), 1981\u20131992 (2014)","journal-title":"PVLDB"},{"key":"572_CR43","doi-asserted-by":"crossref","unstructured":"Yan, D., Cheng, J., Lu, Y., Ng, W.: Effective techniques for message reduction and load balancing in distributed graph computation. In: WWW, pp. 1307\u20131317 (2015)","DOI":"10.1145\/2736277.2741096"},{"key":"572_CR44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58217-7","volume-title":"Systems for Big Graph Analytics. Springer Briefs in Computer Science","author":"D Yan","year":"2017","unstructured":"Yan, D., Tian, Y., Cheng, J.: Systems for Big Graph Analytics. Springer Briefs in Computer Science. Springer, Berlin (2017)"},{"key":"572_CR45","doi-asserted-by":"crossref","unstructured":"Yang, Y., Yan, D., Wu, H., Cheng, J., Zhou, S., Lui, J.C.S.: Diversified temporal subgraph pattern mining. In: SIGKDD, pp. 1965\u20131974 (2016)","DOI":"10.1145\/2939672.2939848"},{"key":"572_CR46","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, pp. 1601\u20131606 (2013)","DOI":"10.1145\/2505515.2505724"},{"issue":"4","key":"572_CR47","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00778-011-0256-4","volume":"21","author":"H Yildirim","year":"2012","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: a scalable index for reachability queries in very large graphs. VLDB J. 21(4), 509\u2013534 (2012)","journal-title":"VLDB J."},{"key":"572_CR48","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: DAGGER: a scalable index for reachability queries in large dynamic graphs. CoRR arxiv:1301.0977 (2013)"},{"key":"572_CR49","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/978-1-4419-6045-0_6","volume-title":"Managing and Mining Graph Data","author":"Jeffrey Xu Yu","year":"2010","unstructured":"Yu, J.X., Cheng, J.: Graph reachability queries: a survey. In: Managing and Mining Graph Data, pp. 181\u2013215 (2010)"},{"key":"572_CR50","unstructured":"Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauly, M., Franklin, M.J., Shenker, S., Stoica, I.: Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing. In: NSDI, pp. 15\u201328 (2012)"},{"issue":"1","key":"572_CR51","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/s41019-016-0023-z","volume":"2","author":"X Zhang","year":"2017","unstructured":"Zhang, X., Chen, L.: Distance-aware selective online query processing over large distributed graphs. Data Sci. Eng. 2(1), 2\u201321 (2017)","journal-title":"Data Sci. Eng."},{"key":"572_CR52","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 (2014)","DOI":"10.1145\/2588555.2612181"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00572-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-019-00572-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-019-00572-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T00:42:56Z","timestamp":1695256976000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-019-00572-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,28]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["572"],"URL":"https:\/\/doi.org\/10.1007\/s00778-019-00572-x","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,28]]},"assertion":[{"value":"9 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}