{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T11:07:45Z","timestamp":1778497665330,"version":"3.51.4"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T00:00:00Z","timestamp":1496188800000},"content-version":"unspecified","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":[[2018,2]]},"DOI":"10.1007\/s00778-017-0468-3","type":"journal-article","created":{"date-parts":[[2017,5,31]],"date-time":"2017-05-31T07:54:55Z","timestamp":1496217295000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":41,"title":["Reachability querying: an independent permutation labeling approach"],"prefix":"10.1007","volume":"27","author":[{"given":"Hao","family":"Wei","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Can","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruoming","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,5,31]]},"reference":[{"key":"468_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: FOCS (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"468_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: Proceedings of SIGMOD\u201989 (1989)","DOI":"10.1145\/67544.66950"},{"issue":"2","key":"468_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/1480506.1480511","volume":"42","author":"P Boldi","year":"2008","unstructured":"Boldi, P., Santini, M., Vigna, S.: A large time-aware web graph. SIGIR Forum 42(2), 33\u201338 (2008)","journal-title":"SIGIR Forum"},{"issue":"5","key":"468_CR4","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1109\/TKDE.2009.117","volume":"22","author":"R Bramandia","year":"2010","unstructured":"Bramandia, R., Choi, B., Ng, W.K.: Incremental maintenance of 2-hop labeling of large graphs. IEEE Trans. Knowl. Data Eng. 22(5), 682\u2013698 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"468_CR5","unstructured":"Broder, A.: On the resemblance and containment of documents. In: Proceedings of SEQUENCES\u201997 (1997)"},{"key":"468_CR6","doi-asserted-by":"crossref","unstructured":"Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. In: Proceedings of STOC\u201998 (1998)","DOI":"10.1145\/276698.276781"},{"key":"468_CR7","doi-asserted-by":"crossref","unstructured":"Cai, J., Poon, C.K.: Path-hop: efficiently indexing large graphs for reachability queries. In: Proceedings of CIKM\u201910 (2010)","DOI":"10.1145\/1871437.1871457"},{"key":"468_CR8","doi-asserted-by":"crossref","unstructured":"Cha, M., Haddadi, H., Benevenuto, F., Gummadi, P.K.: Measuring user influence in twitter: the million follower fallacy. In: Proceedings of ICWSM\u201910 (2010)","DOI":"10.1609\/icwsm.v4i1.14033"},{"key":"468_CR9","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on dags. In: Proceedings of VLDB\u201905 (2005)"},{"key":"468_CR10","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: An efficient algorithm for answering graph reachability queries. In: Proceedings of ICDE\u201908 (2008)","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"468_CR11","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: Decomposing dags into spanning trees: a new way to compress transitive closures. In: Proceedings of ICDE\u201911 (2011)","DOI":"10.1109\/ICDE.2011.5767832"},{"key":"468_CR12","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: Proceedings of SIGMOD\u201913 (2013)","DOI":"10.1145\/2463676.2465286"},{"issue":"11","key":"468_CR13","first-page":"1292","volume":"5","author":"J Cheng","year":"2012","unstructured":"Cheng, J., Shang, Z., Cheng, H., Wang, K., Yu, J.X.: K-reach: who is in your small world. PVLDB 5(11), 1292\u20131303 (2012)","journal-title":"PVLDB"},{"key":"468_CR14","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: Proceedings of EDBT\u201906 (2006)","DOI":"10.1007\/11687238_56"},{"key":"468_CR15","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: Proceedings of EDBT\u201908 (2008)","DOI":"10.1145\/1353343.1353370"},{"issue":"3","key":"468_CR16","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E Cohen","year":"1997","unstructured":"Cohen, E.: Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. 55(3), 441\u2013453 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"468_CR17","doi-asserted-by":"crossref","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proceedings of SODA\u201902 (2002)","DOI":"10.1137\/S0097539702403098"},{"key":"468_CR18","doi-asserted-by":"crossref","unstructured":"Cohen, E., Kaplan, H.: Summarizing data using bottom-k sketches. In: PODC (2007)","DOI":"10.1145\/1281100.1281133"},{"issue":"1","key":"468_CR19","first-page":"213","volume":"1","author":"E Cohen","year":"2008","unstructured":"Cohen, E., Kaplan, H.: Tighter estimation using bottom k sketches. PVLDB 1(1), 213\u2013224 (2008)","journal-title":"PVLDB"},{"issue":"4","key":"468_CR20","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/316194.316229","volume":"29","author":"M Faloutsos","year":"1999","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. ACM SIGCOMM Comput. Commun. Rev. 29(4), 251\u2013262 (1999)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"468_CR21","volume-title":"Statistical Tables for Biological, Agricultural and Medical Research","author":"RA Fisher","year":"1949","unstructured":"Fisher, R.A., Yates, F., et al.: Statistical Tables for Biological, Agricultural and Medical Research, 3rd edn. Oliver and Boyd, Edinburgh (1949)","edition":"3"},{"issue":"4","key":"468_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":"468_CR23","doi-asserted-by":"crossref","unstructured":"Jin, R., Ruan, N., Dey, S., Yu, J.\u00a0X.: Scarab: scaling reachability computation on large graphs. In: Proceedings of SIGMOD\u201912 (2012)","DOI":"10.1145\/2213836.2213856"},{"key":"468_CR24","doi-asserted-by":"publisher","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). doi: 10.1145\/1929934.1929941","DOI":"10.1145\/1929934.1929941"},{"key":"468_CR25","doi-asserted-by":"crossref","unstructured":"Jin, R., Wang, G.: Simple, fast, and scalable reachability oracle. PVLDB 6(14), 1978\u20131989 (2013)","DOI":"10.14778\/2556549.2556578"},{"key":"468_CR26","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Fuhry, D.: 3-HOP: A high-compression indexing scheme for reachability query. In: Proceedings of SIGMOD\u201909 (2009)","DOI":"10.1145\/1559845.1559930"},{"key":"468_CR27","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: Proceedings of SIGMOD\u201908 (2008)","DOI":"10.1145\/1376616.1376677"},{"key":"468_CR28","volume-title":"The Art of Computer Programming, Volume 2: Seminumerical Algorithms","author":"DE Knuth","year":"1981","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston (1981)"},{"key":"468_CR29","doi-asserted-by":"publisher","unstructured":"Lacki, J.: Improved deterministic algorithms for decremental reachability and strongly connected components. ACM Trans. Algorithms 9(3), 27:1\u201327:15 (2013). doi: 10.1145\/2483699.2483707","DOI":"10.1145\/2483699.2483707"},{"key":"468_CR30","doi-asserted-by":"crossref","unstructured":"Roditty, L.: Decremental maintenance of strongly connected components. In: Proceedings of SODA (2013)","DOI":"10.1137\/1.9781611973105.82"},{"key":"468_CR31","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Hopi: An efficient connection index for complex XML document collections. In: Proceedings of EDBT\u201904 (2004)","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"468_CR32","doi-asserted-by":"crossref","unstructured":"Seufert, S., Anand, A., Bedathur, S.\u00a0J., Weikum, G.: Ferrari: Flexible and efficient reachability range assignment for graph indexing. In: Proceedings of ICDE\u201913 (2013)","DOI":"10.1109\/ICDE.2013.6544893"},{"issue":"1\u20133","key":"468_CR33","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":"468_CR34","doi-asserted-by":"crossref","unstructured":"Tri\u00dfI, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: Proceedings of SIGMOD\u201907 (2007)","DOI":"10.1145\/1247480.1247573"},{"key":"468_CR35","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., de\u00a0Moor, O.: A memory efficient reachability data structure through bit vector compression. In: Proceedings of SIGMOD\u201911 (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"468_CR36","unstructured":"Veloso, R.R., Cerf, L., W, M. Jr.: Zaki, M.J.: Reachability queries in very large graphs: A fast refined online search approach. In: Proceedings of EDBT (2014)"},{"key":"468_CR37","unstructured":"Wang, H., He, H., Yang, J., Yu, P.\u00a0S., Yu, J.\u00a0X.: Dual labeling: answering graph reachability queries in constant time. In: Proceedings of ICDE\u201906 (2006)"},{"issue":"12","key":"468_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":"1","key":"468_CR39","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"},{"issue":"4","key":"468_CR40","doi-asserted-by":"crossref","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":"468_CR41","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.\u00a0J.: Dagger: a scalable index for reachability queries in large dynamic graphs. arXiv preprint arXiv:1301.0977 (2013)"},{"key":"468_CR42","doi-asserted-by":"crossref","unstructured":"Yu, J.\u00a0X., Cheng, J.: Graph reachability queries: A survey. In: Aggarwal, C.C., Wang, H. (eds.) Managing and Mining Graph Data, pp. 181\u2013215. Springer (2010)","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"468_CR43","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Yu, J.\u00a0X., Qin, L., Zhu, Q., Zhou, X.: I\/o cost minimization: reachability queries processing over massive graphs. In: Proceedings of EDBT\u201912 (2012)","DOI":"10.1145\/2247596.2247651"},{"key":"468_CR44","doi-asserted-by":"crossref","unstructured":"Zhu, A.\u00a0D., Lin, W., Wang, S., Xiao, X.: Reachability queries on large dynamic graphs: a total order approach. In: Proceedings of the 2014 ACM SIGMOD (2014)","DOI":"10.1145\/2588555.2612181"},{"key":"468_CR45","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 (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\/article\/10.1007\/s00778-017-0468-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0468-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0468-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T20:44:14Z","timestamp":1692823454000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-017-0468-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,31]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["468"],"URL":"https:\/\/doi.org\/10.1007\/s00778-017-0468-3","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,31]]}}}