{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T18:08:34Z","timestamp":1765303714416,"version":"3.40.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T00:00:00Z","timestamp":1386720000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00778-013-0346-6","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T05:13:12Z","timestamp":1386652392000},"page":"227-252","source":"Crossref","is-referenced-by-count":27,"title":["Efficient processing of $$k$$ k -hop reachability queries"],"prefix":"10.1007","volume":"23","author":[{"given":"James","family":"Cheng","sequence":"first","affiliation":[]},{"given":"Zechao","family":"Shang","sequence":"additional","affiliation":[]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,12,11]]},"reference":[{"key":"346_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.F.: Highway dimension, shortest paths, and provably efficient algorithms. In SODA, pp. 782\u2013793 (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"346_CR2","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 Conference, pp. 253\u2013262 (1989)","DOI":"10.1145\/66926.66950"},{"key":"346_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. To appear in SIGMOD Conference (2013)","DOI":"10.1145\/2463676.2465315"},{"key":"346_CR4","doi-asserted-by":"crossref","unstructured":"Boldi, P., Rosa, M., Vigna, S.: Hyperanf: approximating the neighbourhood function of very large graphs on a budget. In WWW, pp. 625\u2013634 (2011)","DOI":"10.1145\/1963405.1963493"},{"key":"346_CR5","doi-asserted-by":"crossref","unstructured":"Bramandia, R., Choi, B., Ng, W.K.: On incremental maintenance of 2-hop labeling of graphs. In WWW, pp. 845\u2013854 (2008)","DOI":"10.1145\/1367497.1367611"},{"key":"346_CR6","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on DAGs. In VLDB, pp. 493\u2013504 (2005)"},{"key":"346_CR7","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":"346_CR8","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: Decomposing DAGs into spanning trees: A new way to compress transitive closures. In ICDE, pp. 1007\u20131018 (2011)","DOI":"10.1109\/ICDE.2011.5767832"},{"key":"346_CR9","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y., Chu, S., Cheng, C.: Efficient processing of distance queries in large graphs: A vertex cover approach. In SIGMOD Conference, pp. 457\u2013468 (2012)","DOI":"10.1145\/2213836.2213888"},{"key":"346_CR10","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y., Fu, A.W.-C., Yu, J.X., Zhu, L.: Finding maximal cliques in massive networks by h*-graph. In SIGMOD Conference, pp. 447\u2013458 (2010)","DOI":"10.1145\/1807167.1807217"},{"issue":"11","key":"346_CR11","first-page":"1292","volume":"5","author":"J Cheng","year":"2012","unstructured":"Cheng, J., Shang, Z., Cheng, H., Wang, H., Yu, J.X.: K-reach: Who is in your small world. PVLDB 5(11), 1292\u20131303 (2012)","journal-title":"PVLDB"},{"key":"346_CR12","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X.: On-line exact shortest distance query processing. In EDBT, pp. 481\u2013492 (2009)","DOI":"10.1145\/1516360.1516417"},{"key":"346_CR13","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X., Lin, X., Wang, H., Yu, P.S.: Fast computation of reachability labeling for large graphs. In EDBT, pp. 961\u2013979 (2006)","DOI":"10.1007\/11687238_56"},{"key":"346_CR14","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X., Lin, X., Wang, H., Yu, P.S.: Fast computing reachability labelings for large graphs with high compression rate. In EDBT, pp. 193\u2013204 (2008)","DOI":"10.1145\/1353343.1353370"},{"key":"346_CR15","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X., Tang, N.: Fast reachability query processing. In DASFAA, pp. 674\u2013688 (2006)","DOI":"10.1007\/11733836_47"},{"key":"346_CR16","doi-asserted-by":"crossref","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In SODA, pp. 937\u2013946 (2002)","DOI":"10.1137\/S0097539702403098"},{"key":"346_CR17","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press,Cambridge, MA (2009)","edition":"3"},{"issue":"21","key":"346_CR18","doi-asserted-by":"crossref","first-page":"4633","DOI":"10.1103\/PhysRevLett.85.4633","volume":"85","author":"SN Dorogovtsev","year":"2000","unstructured":"Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N.: Structure of growing networks with preferential linking. Phys. Rev. Lett. 85(21), 4633\u20134636 (2000)","journal-title":"Phys. Rev. Lett."},{"key":"346_CR19","doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In SIGCOMM, pp. 251\u2013262 (1999)","DOI":"10.1145\/316194.316229"},{"issue":"4","key":"346_CR20","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"346_CR21","volume-title":"Approximation Algorithms for NP-hard Problems","author":"DS Hochbaum","year":"1997","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-hard Problems. PWS Publishing Co., Boston, MA, USA (1997)"},{"issue":"4","key":"346_CR22","doi-asserted-by":"crossref","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":"346_CR23","doi-asserted-by":"crossref","unstructured":"Jin, R., Hong, H., Wang, H., Ruan, N., Xiang, Y.: Computing label-constraint reachability in graph databases. In SIGMOD Conference, pp. 123\u2013134 (2010)","DOI":"10.1145\/1807167.1807183"},{"issue":"9","key":"346_CR24","first-page":"551","volume":"4","author":"R Jin","year":"2011","unstructured":"Jin, R., Liu, L., Ding, B., Wang, H.: Distance-constraint reachability computation in uncertain graphs. PVLDB 4(9), 551\u2013562 (2011)","journal-title":"PVLDB"},{"key":"346_CR25","doi-asserted-by":"crossref","unstructured":"Jin, R., Ruan, N., Xiang, Y., Lee, V.E.: A highway-centric labeling approach for answering distance queries on large sparse graphs. In SIGMOD Conference, pp. 445\u2013456 (2012)","DOI":"10.1145\/2213836.2213887"},{"issue":"1","key":"346_CR26","first-page":"7","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 (2011)","journal-title":"ACM Trans. Database Syst."},{"key":"346_CR27","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 Conference, pp. 813\u2013826 (2009)","DOI":"10.1145\/1559845.1559930"},{"key":"346_CR28","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In SIGMOD Conference, pp. 595\u2013608 (2008)","DOI":"10.1145\/1376616.1376677"},{"issue":"2","key":"346_CR29","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"MEJ Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167\u2013256 (2003)","journal-title":"SIAM Rev."},{"issue":"1\u20133","key":"346_CR30","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(88)90032-1","volume":"58","author":"K Simon","year":"1988","unstructured":"Simon, K.: An improved algorithm for transitive closure on acyclic digraphs. Theor. Comput. Sci. 58(1\u20133), 325\u2013346 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"346_CR31","doi-asserted-by":"crossref","unstructured":"Stann, F., Heidemann, J.: Rmst: Reliable data transport in sensor networks. In 1st IEEE International Workshop on Sensor Net Protocols and Applications, pp. 102\u2013112 (2003)","DOI":"10.1109\/SNPA.2003.1203361"},{"key":"346_CR32","doi-asserted-by":"crossref","unstructured":"Tri\u00dfl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In SIGMOD Conference, pp. 845\u2013856 (2007)","DOI":"10.1145\/1247480.1247573"},{"key":"346_CR33","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., de Moor, O.: A memory efficient reachability data structure through bit vector compression. In SIGMOD Conference, pp. 913\u2013924 (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"346_CR34","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, p. 75 (2006)","DOI":"10.1109\/ICDE.2006.53"},{"key":"346_CR35","doi-asserted-by":"crossref","unstructured":"Wei, F.: TEDI: Efficient shortest path query answering on graphs. In SIGMOD Conference, pp. 99\u2013110 (2010)","DOI":"10.1145\/1807167.1807181"},{"key":"346_CR36","doi-asserted-by":"crossref","unstructured":"Xiao, Y., Wu, W., Pei, J., Wang, W., He, Z.: Efficiently indexing shortest paths by exploiting symmetry in graphs. In EDBT, pp. 493\u2013504 (2009)","DOI":"10.1145\/1516360.1516418"},{"issue":"1","key":"346_CR37","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), 276\u2013284 (2010)","journal-title":"PVLDB"},{"key":"346_CR38","doi-asserted-by":"crossref","unstructured":"Zhu, L., Choi, B., He, B., Yu, J.X., Ng, W.K.: A uniform framework for ad-hoc indexes to answer reachability queries on large graphs. In DASFAA, pp. 138\u2013152 (2009)","DOI":"10.1007\/978-3-642-00887-0_12"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-013-0346-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-013-0346-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-013-0346-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T03:52:34Z","timestamp":1746071554000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-013-0346-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,11]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["346"],"URL":"https:\/\/doi.org\/10.1007\/s00778-013-0346-6","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2013,12,11]]}}}