{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:35:45Z","timestamp":1774949745020,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T00:00:00Z","timestamp":1346112000000},"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":[[2013,6]]},"DOI":"10.1007\/s00778-012-0288-4","type":"journal-article","created":{"date-parts":[[2012,8,27]],"date-time":"2012-08-27T07:51:39Z","timestamp":1346053899000},"page":"275-294","source":"Crossref","is-referenced-by-count":8,"title":["Computing weight constraint reachability in large networks"],"prefix":"10.1007","volume":"22","author":[{"given":"Miao","family":"Qiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip S.","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,28]]},"reference":[{"key":"288_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: Proceedings of the 1989 ACM SIGMOD international conference on Management of data (SIGMOD 1989), pp. 253\u2013262 (1989)","DOI":"10.1145\/66926.66950"},{"key":"288_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1186\/1471-2105-8-335","volume":"8","author":"G Bebek","year":"2007","unstructured":"Bebek, G., Yang, J.: PathFinder: Mining signal transduction pathway segments from protein-protein interaction networks. BMC Bioinform. J. 8, 335 (2007)","journal-title":"BMC Bioinform. J."},{"key":"288_CR3","doi-asserted-by":"crossref","unstructured":"Bender, M. A., Farach-Colton, M.: The LCA problem revisited. In: LATIN 2000: Theoretical Informatics, volume 1776 of Lecture Notes in Computer Science, pp. 88\u201394. Springer, Berlin\/Heidelberg","DOI":"10.1007\/10719839_9"},{"key":"288_CR4","doi-asserted-by":"crossref","unstructured":"Bramandia, R., Choi, B., Ng, W.K.: On incremental maintenance of 2-hop labeling of graphs. In: Proceedings of the 17th international conference on World Wide Web (WWW 2008), pp. 845\u2013854 (2008)","DOI":"10.1145\/1367497.1367611"},{"key":"288_CR5","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: An efficient algorithm for answering graph reachability queries. In: Proceedings of the 24th International Conference on Data Engineering (ICDE 2008), pp. 893\u2013902 (2008)","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"288_CR6","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 the 11th International Conference on Extending Database Technology (EDBT 2008), pp. 193\u2013204 (2008)","DOI":"10.1145\/1353343.1353370"},{"key":"288_CR7","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 937\u2013946 (2002)"},{"key":"288_CR8","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, New York (2001)"},{"key":"288_CR9","doi-asserted-by":"crossref","unstructured":"Fan, W., Li, J., Ma, S., Tang, N., Wu, Y.: Adding regular expressions to graph reachability and pattern queries. In: Proceedings of the 27th International Conference on Data Engineering (ICDE 2011), pp. 39\u201350 (2011)","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"288_CR10","doi-asserted-by":"crossref","unstructured":"Florescu, D., Levy, A.Y., Suciu, D.: Query containment for conjunctive queries with regular expressions. In: Proceedings of the 1998 Symposium on Principles of Database Systems (PODS 1998), pp. 139\u2013148 (1998)","DOI":"10.1145\/275487.275503"},{"key":"288_CR11","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi terminal network flows. J. Soc. Ind. Appl. Math. 9, 551\u2013571 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"288_CR12","doi-asserted-by":"crossref","unstructured":"He, H., Wang, H., Yang, J., Yu, P. S.: Compact reachability labeling for graph-structured data. In: Proceedings of the 2005 ACM CIKM International Conference on Information and Knowledge Management (CIKM 2005), pp. 594\u2013601 (2005)","DOI":"10.1145\/1099554.1099708"},{"issue":"4","key":"288_CR13","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":"288_CR14","doi-asserted-by":"crossref","unstructured":"Jin, R., Hong, H., Wang, H., Ruan, N., Xiang, Y.: Computing label-constraint reachability in graph databases. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD 2010), pp. 123\u2013134 (2010)","DOI":"10.1145\/1807167.1807183"},{"issue":"9","key":"288_CR15","doi-asserted-by":"crossref","first-page":"551","DOI":"10.14778\/2002938.2002941","volume":"4","author":"R Jin","year":"2011","unstructured":"Jin, R., Liu, L., Ding, B., Wang, H.: Distance-constraint reachability computation in uncertain graphs. Proc. VLDB Endowment (PVLDB 2011) 4(9), 551\u2013562 (2011)","journal-title":"Proc. VLDB Endowment (PVLDB 2011)"},{"key":"288_CR16","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 the 2009 ACM SIGMOD International Conference on Management of Data (SIGMOD 2009), pp. 813\u2013826 (2009)","DOI":"10.1145\/1559845.1559930"},{"key":"288_CR17","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 the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD 2008), pp. 595\u2013608 (2008)","DOI":"10.1145\/1376616.1376677"},{"key":"288_CR18","doi-asserted-by":"crossref","unstructured":"Johnsonbaugh, R., Kalin, M.: A graph generation software package. In: Proceedings of the 22nd SIGCSE Technical Symposium on Computer Science Education (SIGCSE 1991), pp. 151\u2013154 (1991)","DOI":"10.1145\/107005.107032"},{"issue":"1","key":"288_CR19","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Amer. Math. Soc."},{"issue":"1","key":"288_CR20","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/373626.373678","volume":"30","author":"JK Lawder","year":"2001","unstructured":"Lawder, J.K., King, P.J.H.: Querying multi-dimensional data indexed using the hilbert space-filling curve. SIGMOD Rec. 30(1), 19\u201324 (2001)","journal-title":"SIGMOD Rec."},{"key":"288_CR21","unstructured":"Ma, Q., Steenkiste, P.: On path selection for traffic with bandwidth guarantees. In: Proceedings of the 1997 International Conference on Network Protocols (ICNP 1997), pp. 191\u2013202 (1997)"},{"issue":"6","key":"288_CR22","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/S009753979122370X","volume":"24","author":"AO Mendelzon","year":"1995","unstructured":"Mendelzon, A.O., Wood, P.T.: Finding regular simple paths in graph databases. SIAM J. Comput. 24(6), 1235\u20131258 (1995)","journal-title":"SIAM J. Comput."},{"key":"288_CR23","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1080\/00107510500052444","volume":"46","author":"MEJ Newman","year":"2005","unstructured":"Newman, M.E.J.: Power laws, pareto distributions and zipf\u2019s law. Contemp. Phys. 46, 323\u2013351 (2005)","journal-title":"Contemp. Phys."},{"key":"288_CR24","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceedings of the 36th annual ACM symposium on Theory of computing (STOC 2004), pp. 184\u2013191 (2004)","DOI":"10.1145\/1007352.1007387"},{"key":"288_CR25","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: HOPI: an efficient connection index for complex XML document collections. In: Proceedings of the 9th International Conference on Extending Database Technology (EDBT 2004), pp. 237\u2013255 (2004)","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"288_CR26","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Efficient creation and incremental maintenance of the HOPI index for complex XML document collections. In: Proceedings of the 21th International Conference on Data Engineering (ICDE 2005), pp. 360\u2013371 (2005)","DOI":"10.1109\/ICDE.2005.57"},{"key":"288_CR27","doi-asserted-by":"crossref","unstructured":"Tri\u00dfI, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data (SIGMOD 2007), pp. 845\u2013856 (2007)","DOI":"10.1145\/1247480.1247573"},{"key":"288_CR28","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., de Moor, O.: A memory efficient reachability data structure through bit vector compression. In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data (SIGMOD 2011), pp. 913\u2013924 (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"288_CR29","doi-asserted-by":"crossref","unstructured":"Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P.: On the evolution of user interaction in facebook. In: Proceedings of the 2nd ACM SIGCOMM Workshop on Social Networks (WOSN 2009), pp. 37\u201342 (2009)","DOI":"10.1145\/1592665.1592675"},{"issue":"2","key":"288_CR30","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"JS Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures. ACM Comput. Surv. 33(2), 209\u2013271 (2001)","journal-title":"ACM Comput. Surv."},{"key":"288_CR31","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: Proceedings of the 22th International Conference on Data Engineering (ICDE 2006), pp. 75 (2006)","DOI":"10.1109\/ICDE.2006.53"},{"key":"288_CR32","doi-asserted-by":"crossref","unstructured":"Xu, K., Zou, L., Yu, J. X., Chen, L., Xiao, Y., Zhao, D.: Answering label-constraint reachability in large graphs. In: Proceedings of the 2011 ACM CIKM International Conference on Information and Knowledge Management (CIKM 2011), pp. 1595\u20131600 (2011)","DOI":"10.1145\/2063576.2063807"},{"issue":"1","key":"288_CR33","doi-asserted-by":"crossref","first-page":"276","DOI":"10.14778\/1920841.1920879","volume":"3","author":"H Yildirim","year":"2010","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: scalable reachability index for large graphs. Proc. VLDB Endowment (PVLDB 2010) 3(1), 276\u2013284 (2010)","journal-title":"Proc. VLDB Endowment (PVLDB 2010)"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-012-0288-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-012-0288-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-012-0288-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,3]],"date-time":"2019-07-03T00:26:55Z","timestamp":1562113615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-012-0288-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,28]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["288"],"URL":"https:\/\/doi.org\/10.1007\/s00778-012-0288-4","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,28]]}}}