{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T16:40:55Z","timestamp":1742920855288,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642008863"},{"type":"electronic","value":"9783642008870"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00887-0_12","type":"book-chapter","created":{"date-parts":[[2009,3,19]],"date-time":"2009-03-19T13:49:36Z","timestamp":1237470576000},"page":"138-152","source":"Crossref","is-referenced-by-count":9,"title":["A Uniform Framework for Ad-Hoc Indexes to Answer Reachability Queries on Large Graphs"],"prefix":"10.1007","author":[{"given":"Linhong","family":"Zhu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Byron","family":"Choi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingsheng","family":"He","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wee Keong","family":"Ng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"W3C: OWL web ontology language overview, http:\/\/www.w3.org\/TR\/owl-features"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Wu, X., Lee, M.L., Hsu, W.: A prime number labeling scheme for dynamic ordered xml trees. In: ICDE, pp. 66\u201378 (2004)","DOI":"10.1109\/ICDE.2004.1319985"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Dietz, P.F.: Maintaining order in a linked list. In: STOC, pp. 122\u2013127 (1982)","DOI":"10.1145\/800070.802184"},{"key":"12_CR4","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Efficient algorithms for pattern matching on directed acyclic graphs. In: ICDE, pp. 384\u2013385 (2005)"},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1007\/11733836_56","volume-title":"Database Systems for Advanced Applications","author":"G. Wu","year":"2006","unstructured":"Wu, G., Zhang, K., Liu, C., Li, J.: Adapting prime number labeling scheme for directed acyclic graphs. In: Li Lee, M., Tan, K.-L., Wuwongse, V. (eds.) DASFAA 2006. LNCS, vol.\u00a03882, pp. 787\u2013796. Springer, Heidelberg (2006)"},{"key":"12_CR6","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on dags. In: VLDB, pp. 493\u2013504 (2005)"},{"key":"12_CR7","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"},{"key":"12_CR8","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":"5","key":"12_CR9","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.\u00a032(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"key":"12_CR10","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Efficient creation and incremental maintenance of the hopi index for complex xml document collections. In: ICDE, pp. 360\u2013371 (2005)"},{"key":"12_CR11","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, pp. 75\u201375 (2006)","DOI":"10.1109\/ICDE.2006.53"},{"key":"12_CR12","unstructured":"Gibson, D., Kumar, R., Tomkins, A.: Discovering large dense subgraphs in massive graphs. In: VLDB, pp. 721\u2013732 (2005)"},{"key":"12_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1007\/11687238_56","volume-title":"Advances in Database Technology - EDBT 2006","author":"J. Cheng","year":"2006","unstructured":"Cheng, J., Yu, J.X., Lin, X., Wang, H., Yu, P.S.: Fast computation of reachability labeling for large graphs. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., B\u00f6hm, K., Kemper, A., Grust, T., B\u00f6hm, C. (eds.) EDBT 2006. LNCS, vol.\u00a03896, pp. 961\u2013979. Springer, Heidelberg (2006)"},{"key":"12_CR14","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"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"He, H., Wang, H., Yang, J., Yu, P.S.: Compact reachability labeling for graph-structured data. In: CIKM (2005)","DOI":"10.1145\/1099554.1099708"},{"issue":"1","key":"12_CR16","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"B.W. Kernighan","year":"1970","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. The Bell system technical journal\u00a049(1), 291\u2013307 (1970)","journal-title":"The Bell system technical journal"},{"key":"12_CR17","unstructured":"Karypis lab: Family of Multilevel Partitioning Algorithms, http:\/\/glaros.dtc.umn.edu\/gkhome\/metis\/metis\/overview"},{"issue":"3","key":"12_CR18","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A. Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl.\u00a011(3), 430\u2013452 (1990)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"2","key":"12_CR19","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput.\u00a01(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-540-24741-8_15","volume-title":"Advances in Database Technology - EDBT 2004","author":"R. Schenkel","year":"2004","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: Hopi: An efficient connection index for complex xml document collections. In: Bertino, E., Christodoulakis, S., Plexousakis, D., Christophides, V., Koubarakis, M., B\u00f6hm, K., Ferrari, E. (eds.) EDBT 2004. LNCS, vol.\u00a02992, pp. 237\u2013255. Springer, Heidelberg (2004)"},{"key":"12_CR21","unstructured":"Batagelj, V., Mrvar, A.: Pajek datasets, http:\/\/vlado.fmf.uni-lj.si\/pub\/networks\/data\/"}],"container-title":["Lecture Notes in Computer Science","Database Systems for Advanced Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00887-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T15:25:59Z","timestamp":1739028359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00887-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642008863","9783642008870"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00887-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}