{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:27Z","timestamp":1759063587896},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,5,17]],"date-time":"2011-05-17T00:00:00Z","timestamp":1305590400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9528-z","type":"journal-article","created":{"date-parts":[[2011,5,16]],"date-time":"2011-05-16T19:54:18Z","timestamp":1305575658000},"page":"201-223","source":"Crossref","is-referenced-by-count":6,"title":["Succinct and I\/O Efficient Data Structures for Traversal in Trees"],"prefix":"10.1007","volume":"63","author":[{"given":"Craig","family":"Dillabaugh","sequence":"first","affiliation":[]},{"given":"Meng","family":"He","sequence":"additional","affiliation":[]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,17]]},"reference":[{"key":"9528_CR1","first-page":"117","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., Arge, L., Murali, T.M., Varadarajan, K.R., Vitter, J.S.: I\/O-efficient algorithms for contour-line extraction and planar graph blocking (extended abstract). In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 117\u2013126. Society for Industrial and Applied Mathematics, Philadelphia (1998)"},{"issue":"9","key":"9528_CR2","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"9528_CR3","unstructured":"Alstrup, S., Bender, M.A., Demaine, E.D., Farach-Colton, M., Rauhe, T., Thorup, M.: Efficient tree layout in a multilevel memory hierarchy. arXiv:cs.DS\/0211010 [cs:DS] (2004)"},{"issue":"4","key":"9528_CR4","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00453-004-1146-6","volume":"43","author":"D. Benoit","year":"2005","unstructured":"Benoit, D., Demaine, E.D., Munro, J., Raman, R., Raman, V., Rao, S.S.: Representing trees of higher degree. Algorithmica 43(4), 275\u2013292 (2005)","journal-title":"Algorithmica"},{"key":"9528_CR5","doi-asserted-by":"crossref","first-page":"581","DOI":"10.1145\/1109557.1109621","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"G.S. Brodal","year":"2006","unstructured":"Brodal, G.S., Fagerberg, R.: Cache-oblivious string dictionaries. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 581\u2013590. Society for Industrial and Applied Mathematics, Philadelphia (2006)"},{"key":"9528_CR6","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1109\/DCC.2008.67","volume-title":"Proceedings of the 18th Data Compression Conference","author":"Y.F. Chien","year":"2008","unstructured":"Chien, Y.F., Hon, W.K., Shah, R., Vitter, J.S.: Geometric Burrows-Wheeler transform: Linking range searching and text indexing. In: Proceedings of the 18th Data Compression Conference, pp. 252\u2013261. IEEE Computer Society, Washington (2008)"},{"key":"9528_CR7","first-page":"383","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"D.R. Clark","year":"1996","unstructured":"Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 383\u2013391. Society for Industrial and Applied Mathematics, Philadelphia (1996)"},{"key":"9528_CR8","unstructured":"Demaine, E.D., Iacono, J., Langerman, S.: Worst-case optimal tree layout in a memory hierarchy. arXiv:cs\/0410048v1 [cs:DS] (2004)"},{"key":"9528_CR9","first-page":"112","volume-title":"Proceedings of the 19th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science","author":"C. Dillabaugh","year":"2008","unstructured":"Dillabaugh, C., He, M., Maheshwari, A.: Succinct and I\/O efficient data structures for traversal in trees. In: Proceedings of the 19th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 5369, pp. 112\u2013123. Springer, Berlin\/Heidelberg (2008)"},{"issue":"2","key":"9528_CR10","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1006\/jagm.1999.1014","volume":"32","author":"J. Gil","year":"1999","unstructured":"Gil, J., Itai, A.: How to pack trees. J. Algorithms 32(2), 108\u2013132 (1999)","journal-title":"J. Algorithms"},{"key":"9528_CR11","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0166-218X(02)00217-2","volume":"126","author":"D.A. Hutchinson","year":"2003","unstructured":"Hutchinson, D.A., Maheshwari, A., Zeh, N.: An external memory data structure for shortest path queries. Discrete Appl. Math. 126, 55\u201382 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9528_CR12","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1109\/SFCS.1989.63533","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science","author":"G. Jacobson","year":"1989","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 549\u2013554. IEEE Computer Society, New York (1989)"},{"issue":"3","key":"9528_CR13","first-page":"28:1","volume":"4","author":"H.I. Lu","year":"2008","unstructured":"Lu, H.I., Yeh, C.C.: Balanced parentheses strike back. ACM Trans. Algorithms 4(3), 28:1\u201328:13 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"9528_CR14","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762\u2013776 (2001)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9528_CR15","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF01940646","volume":"16","author":"M.H. Nodine","year":"1996","unstructured":"Nodine, M.H., Goodrich, M.T., Vitter, J.S.: Blocking for external graph searching. Algorithmica 16(2), 181\u2013214 (1996)","journal-title":"Algorithmica"},{"issue":"4","key":"9528_CR16","doi-asserted-by":"crossref","first-page":"43:1","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R. Raman","year":"2007","unstructured":"Raman, R., Raman, V., Satti, S.R.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43:1\u201343:25 (2007)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9528-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9528-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9528-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T20:36:49Z","timestamp":1560199009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9528-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,17]]},"references-count":16,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9528"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9528-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,17]]}}}