{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:25:03Z","timestamp":1742948703153,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":22,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_61","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:36:50Z","timestamp":1214505410000},"page":"121-123","source":"Crossref","is-referenced-by-count":1,"title":["Cache-Oblivious B-Tree"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"61_CR1_61","doi-asserted-by":"publisher","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":"61_CR2_61","volume-title":"Handbook on Data Structures and Applications","author":"L. Arge","year":"2005","unstructured":"Arge, L., Brodal, G.S., Fagerberg, R.: Cache\u2010oblivious data structures. In: Mehta, D., Sahni, S. (eds.) Handbook on Data Structures and Applications. CRC Press, Boca Raton (2005)"},{"key":"61_CR3_61","first-page":"160","volume-title":"Proc. 21st ACM Symposium on Computational Geometry","author":"L. Arge","year":"2005","unstructured":"Arge, L., Brodal, G.S., Fagerberg, R., Laustsen, M.: Cache\u2010oblivious planar orthogonal range searching and counting. In: Proc. 21st ACM Symposium on Computational Geometry, pp.\u00a0160\u2013169. ACM, New York (2005)"},{"key":"61_CR4_61","first-page":"170","volume-title":"Proc. 21st ACM Symposium on Computational Geometry","author":"L. Arge","year":"2005","unstructured":"Arge, L., de\u00a0Berg, M., Haverkort, H.J.: Cache\u2010oblivious R\u2011trees. In: Proc. 21st ACM Symposium on Computational Geometry, pp.\u00a0170\u2013179. ACM, New York (2005)"},{"issue":"6","key":"61_CR5_61","doi-asserted-by":"publisher","first-page":"1488","DOI":"10.1137\/S009753970240481X","volume":"32","author":"L. Arge","year":"2003","unstructured":"Arge, L., Vitter, J.S.: Optimal external memory interval management. SIAM J.\u00a0Comput. 32(6), 1488\u20131508 (2003)","journal-title":"SIAM J. Comput."},{"key":"61_CR6_61","first-page":"158","volume-title":"Proc. 22nd ACM Symposium on Computational Geometry","author":"L. Arge","year":"2006","unstructured":"Arge, L., Zeh, N.: Simple and semi-dynamic structures for cache\u2010oblivious planar orthogonal range searching. In: Proc. 22nd ACM Symposium on Computational Geometry, pp.\u00a0158\u2013166. ACM, New York (2006)"},{"doi-asserted-by":"crossref","unstructured":"Bender, M., Cole, R., Demaine, E., Farach\u2010Colton, M.: Scanning and traversing: Maintaining data for traversals in a\u00a0memory hierarchy. In: Proc. 10th Annual European Symposium on Algorithms. LNCS, vol.\u00a02461, pp.\u00a0139\u2013151. Springer, Berlin (2002)","key":"61_CR7_61","DOI":"10.1007\/3-540-45749-6_16"},{"key":"61_CR8_61","first-page":"195","volume-title":"Proc. 29th International Colloquium on Automata, Languages, and Programming. LNCS, vol. 2380","author":"M. Bender","year":"2002","unstructured":"Bender, M., Cole, R., Raman, R.: Exponential structures for cache\u2010oblivious algorithms. In: Proc. 29th International Colloquium on Automata, Languages, and Programming. LNCS, vol.\u00a02380, pp.\u00a0195\u2013207. Springer, Berlin (2002)"},{"key":"61_CR9_61","first-page":"271","volume-title":"Proc. 44th Annual IEEE Symposium on Foundations of Computer Science","author":"M.A. Bender","year":"2003","unstructured":"Bender, M.A., Brodal, G.S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J., Lopez-Ortiz, A.: The cost of cache\u2010oblivious searching. In: Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0271\u2013282. IEEE Computer Society Press, Los Alamitos (2003)"},{"issue":"2","key":"61_CR10_61","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/S0097539701389956","volume":"35","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Demaine, E.D., Farach\u2010Colton, M.: Cache\u2010oblivious B\u2011trees. SIAM J.\u00a0Comput. 35(2), 341\u2013358 (2005). Conference version appeared at FOCS (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"61_CR11_61","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.jalgor.2004.04.014","volume":"53","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A\u00a0locality\u2010preserving cache\u2010oblivious dynamic dictionary. J.\u00a0Algorithms 53(2), 115\u2013136 (2004). Conference version appeared at SODA (2002)","journal-title":"J. Algorithms"},{"key":"61_CR12_61","first-page":"81","volume-title":"Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"M.A. Bender","year":"2007","unstructured":"Bender, M.A., Farach\u2010Colton, M., Fineman, J.T., Fogel, Y.R., Kuszmaul, B.C., Nelson, J.: Cache\u2010oblivious streaming B\u2011trees. In: Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures, pp.\u00a081\u201392. ACM, New York (2007)"},{"key":"61_CR13_61","first-page":"233","volume-title":"Proc. 25th ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems","author":"M.A. Bender","year":"2006","unstructured":"Bender, M.A., Farach\u2010Colton, M., Kuszmaul, B.C.: Cache\u2010oblivious string B\u2011trees. In: Proc. 25th ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems, pp.\u00a0233\u2013242. ACM, New York (2006)"},{"key":"61_CR14_61","first-page":"228","volume-title":"Proc. 17th Annual ACM Symposium on Parallel Algorithms","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Fineman, J.T., Gilbert, S., Kuszmaul, B.C.: Concurrent cache\u2010oblivious B\u2011trees. In: Proc. 17th Annual ACM Symposium on Parallel Algorithms, pp.\u00a0228\u2013237. ACM, New York (2005)"},{"key":"61_CR15_61","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1145\/1109557.1109621","volume-title":"SODA: ACM-SIAM Symposium on Discrete Algorithms","author":"G.S. Brodal","year":"2006","unstructured":"Brodal, G.S., Fagerberg, R.: Cache\u2010oblivious string dictionaries. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0581\u2013590. ACM Press, New York (2006)"},{"doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache\u2010oblivious search trees via binary trees of small height. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a039\u201348 ACM, New York (2002)","key":"61_CR16_61","DOI":"10.7146\/brics.v8i36.21696"},{"key":"61_CR17_61","first-page":"114","volume-title":"Proc. Algorithms and Data Structures, 8th International Workshop, WADS. LNCS, vol. 2748","author":"G. Franceschini","year":"2003","unstructured":"Franceschini, G., Grossi, R.: Optimal worst-case operations for implicit cache\u2010oblivious search trees. In: Proc. Algorithms and Data Structures, 8th International Workshop, WADS. LNCS, vol.\u00a02748, pp.\u00a0114\u2013126. Springer, Berlin (2003)"},{"key":"61_CR18_61","first-page":"285","volume-title":"40th Annual IEEE Symposium on Foundations of Computer Science","author":"M. Frigo","year":"1999","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache\u2010oblivious algorithms. In: 40th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0285\u2013298. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"61_CR19_61","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-10843-2_34","volume-title":"Automata, Languages and Programming, 8th Colloquium. LNCS, vol. 115","author":"A. Itai","year":"1981","unstructured":"Itai, A., Konheim, A.G., Rodeh, M.: A\u00a0sparse table implementation of priority queues. In: Automata, Languages and Programming, 8th Colloquium. LNCS, vol.\u00a0115, pp.\u00a0417\u2013431. Springer, Berlin (1981)"},{"key":"61_CR20_61","first-page":"78","volume-title":"Experimental Algorithmics. LNCS, vol. 2547","author":"R.E. Ladner","year":"2000","unstructured":"Ladner, R.E., Fortna, R., B.-Nguyen, H.: A\u00a0comparison of cache aware and cache oblivious static search trees using program instrumentation. In: Experimental Algorithmics. LNCS, vol.\u00a02547, pp.\u00a078\u201392. Springer, Berlin (2000)"},{"unstructured":"Prokop, H.: Cache\u2010oblivious algorithms. Master's thesis, Massachusetts Institute of Technology (1999)","key":"61_CR21_61"},{"key":"61_CR22_61","first-page":"67","volume-title":"Proc. Algorithm Engineering, 5th International Workshop, WAE. LNCS, vol. 2141","author":"N. Rahman","year":"2001","unstructured":"Rahman, N., Cole, R., Raman, R.: Optimised predecessor data structures for internal memory. In: Proc. Algorithm Engineering, 5th International Workshop, WAE. LNCS, vol.\u00a02141, pp.\u00a067\u201378. Springer, Berlin (2001)"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_61","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T02:09:25Z","timestamp":1662170965000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_61"}},"subtitle":["2005; Bender, Demaine, Farach-Colton"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_61","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}