{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:00:35Z","timestamp":1783576835293,"version":"3.55.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,3,9]],"date-time":"2010-03-09T00:00:00Z","timestamp":1268092800000},"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":[[2011,10]]},"DOI":"10.1007\/s00453-010-9394-0","type":"journal-article","created":{"date-parts":[[2010,3,8]],"date-time":"2010-03-08T17:14:25Z","timestamp":1268068465000},"page":"463-505","source":"Crossref","is-referenced-by-count":9,"title":["The Cost of Cache-Oblivious Searching"],"prefix":"10.1007","volume":"61","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongdong","family":"Ge","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simai","family":"He","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haodong","family":"Hu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,3,9]]},"reference":[{"key":"9394_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, P., Arge, L., Danner, A., Holland-Minkley, B.: Cache-oblivious data structures for orthogonal range searching. In: Proc. 19th ACM Symp. on Comp. Geom. (SOCG), pp. 237\u2013245 (2003)","DOI":"10.1145\/777792.777828"},{"issue":"9","key":"9394_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":"9394_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Alpern, B., Chandra, A.K., Snir, M.: A model for hierarchical memory. In: Proc. of the 19th Ann. ACM Symp. on Theory of Computing (STOC), pp. 305\u2013314 (1987)","DOI":"10.1145\/28395.28428"},{"key":"9394_CR4","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Chandra, A.K., Snir, M.: Hierarchical memory with block transfer. In: Proc. of the 28th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 204\u2013216 (1987)","DOI":"10.1109\/SFCS.1987.31"},{"issue":"2\u20133","key":"9394_CR5","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1007\/BF01185206","volume":"12","author":"B. Alpern","year":"1994","unstructured":"Alpern, B., Carter, L., Feig, E., Selker, T.: The uniform memory hierarchy model of computation. Algorithmica 12(2\u20133), 72\u2013109 (1994)","journal-title":"Algorithmica"},{"key":"9394_CR6","unstructured":"Alstrup, S., Bender, M.A., Demaine, E.D., Farach-Colton, M., Munro, J.I., Rauhe, T., Thorup, M.: Efficient tree layout in a multilevel memory hierarchy (2002). arXiv:cs.DS\/0211010"},{"key":"9394_CR7","unstructured":"Andrews, M., Bender, M.A., Zhang, L.: New algorithms for the disk scheduling problem. In: Proc. of the 37th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 580\u2013589 (1996)"},{"issue":"2","key":"9394_CR8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/s00453-001-0071-1","volume":"32","author":"M. Andrews","year":"2002","unstructured":"Andrews, M., Bender, M.A., Zhang, L.: New algorithms for the disk scheduling problem. Algorithmica 32(2), 277\u2013301 (2002)","journal-title":"Algorithmica"},{"key":"9394_CR9","doi-asserted-by":"crossref","unstructured":"Barve, R.D., Vitter, J.S.: A theoretical framework for memory-adaptive algorithms. In: Proc. of the 40th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 273\u2013284 (1999)","DOI":"10.1109\/SFFCS.1999.814599"},{"key":"9394_CR10","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.: Organization and maintenance of large ordered indexes. Acta Inform. 1, 173\u2013189 (1972)","journal-title":"Acta Inform."},{"key":"9394_CR11","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/3-540-45465-9_18","volume-title":"Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"M. Bender","year":"2002","unstructured":"Bender, M., Cole, R., Raman, R.: Exponential structures for cache-oblivious algorithms. In: Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP). LNCS, vol.\u00a02380, pp.\u00a0195\u2013207. Springer, Berlin (2002)"},{"key":"9394_CR12","series-title":"LNCS","first-page":"165","volume-title":"Proc. 10th Annual European Symp. on Algorithms (ESA)","author":"M. Bender","year":"2002","unstructured":"Bender, M., Demaine, E., Farach-Colton, M.: Efficient tree layout in a multilevel memory hierarchy. In: Proc. 10th Annual European Symp. on Algorithms (ESA). LNCS, vol. 2461, pp. 165\u2013173. Springer, Berlin (2002)"},{"key":"9394_CR13","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Brodal, G.S., Fagerberg, R., Ge, D., He, S., Hu, H., Iacono, J., L\u00f3pez-Ortiz, A.: The cost of cache-oblivious searching. In: Proc. 44th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 271\u2013280 (2003)","DOI":"10.1109\/SFCS.2003.1238201"},{"issue":"2","key":"9394_CR14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.jalgor.2004.04.014","volume":"3","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. J. Algorithms 3(2), 115\u2013136 (2004)","journal-title":"J. Algorithms"},{"issue":"2","key":"9394_CR15","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/S0097539701389956","volume":"35","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 35(2), 341\u2013358 (2005)","journal-title":"SIAM J. Comput."},{"key":"9394_CR16","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/1073970.1074009","volume-title":"SPAA \u201905: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"M.A. Bender","year":"2005","unstructured":"Bender, M.A., Fineman, J.T., Gilbert, S., Kuszmaul, B.C.: Concurrent cache-oblivious B-trees. In: SPAA \u201905: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 228\u2013237. ACM, New York (2005)"},{"key":"9394_CR17","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M., Kuszmaul, B.: Cache-oblivious string B-trees. In: Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 233\u2013242 (2006)","DOI":"10.1145\/1142351.1142385"},{"key":"9394_CR18","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M., Fineman, J.T., Fogel, Y.R., Kuszmaul, B.C., Nelson, J.: Cache-oblivious streaming B-trees. In: SPAA, pp. 81\u201392 (2007)","DOI":"10.1145\/1248377.1248393"},{"key":"9394_CR19","series-title":"LNCS","first-page":"219","volume-title":"Proc. 13th Ann. International Symp. on Algorithms and Computation (ISAAC)","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: Funnel heap\u2014a cache oblivious priority queue. In: Proc. 13th Ann. International Symp. on Algorithms and Computation (ISAAC). LNCS, vol. 2518, pp. 219\u2013228. Springer, Berlin (2002)"},{"key":"9394_CR20","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/3-540-45465-9_37","volume-title":"Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: Cache oblivious distribution sweeping. In: Proc. 29th International Colloquium on Automata, Languages, and Programming (ICALP). LNCS, vol. 2380, pp. 426\u2013438. Springer, Berlin (2002)"},{"key":"9394_CR21","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R., Jacob, R.: Cache oblivious search trees via binary trees of small height. In: Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 39\u201348 (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"key":"9394_CR22","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Demaine, E.D., Fineman, J.T., Iacono, J., Langerman, S., Munro, J.I.: Cache-oblivious dynamic dictionaries with optimal update\/query tradeoff. In: Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1448\u20131456 (2010)","DOI":"10.1137\/1.9781611973075.117"},{"issue":"2","key":"9394_CR23","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/356770.356776","volume":"11","author":"D. Comer","year":"1979","unstructured":"Comer, D.: The ubiquitous B-tree. ACM Computing Surveys 11(2), 121\u2013137 (1979)","journal-title":"ACM Computing Surveys"},{"key":"9394_CR24","unstructured":"Demaine, E.D.: Cache-oblivious algorithms and data structures. In: Lecture Notes from the EEF Summer School on Massive Data Sets (2002)"},{"key":"9394_CR25","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1007\/978-3-540-45078-8_11","volume-title":"Proc. 8th International Workshop on Algorithms and Data Structures (WADS)","author":"G. Franceschini","year":"2003","unstructured":"Franceschini, G., Grossi, R.: Optimal worst-case operations for implicit cache-oblivious search trees. In: Proc. 8th International Workshop on Algorithms and Data Structures (WADS). LNCS, vol. 2748, pp. 114\u2013126. Springer, Berlin (2003)"},{"issue":"2","key":"9394_CR26","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s00224-005-1167-9","volume":"39","author":"G. Franceschini","year":"2006","unstructured":"Franceschini, G., Grossi, R.: Optimal implicit dictionaries over unbounded universes. Theory Comput. Syst. 39(2), 321\u2013345 (2006)","journal-title":"Theory Comput. Syst."},{"key":"9394_CR27","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: 40th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 285\u2013297 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"9394_CR28","doi-asserted-by":"crossref","unstructured":"Hong, J.-W., Kung, H.T.: I\/O complexity: The red-blue pebble game. In: Proc. of the 13th Ann. ACM Symp. on Theory of Computation (STOC), pp. 326\u2013333 (1981)","DOI":"10.1145\/800076.802486"},{"key":"9394_CR29","volume-title":"The Art of Computer Programming: Fundamental Algorithms","author":"D.E. Knuth","year":"1997","unstructured":"Knuth, D.E.: The Art of Computer Programming: Fundamental Algorithms, vol. 1, 3rd edn. Addison-Wesley, Reading (1997)","edition":"3"},{"key":"9394_CR30","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/3-540-36574-5_9","volume-title":"Algorithms for Memory Hierarchies","author":"P. Kumar","year":"2003","unstructured":"Kumar, P.: Cache oblivious algorithms. In: Meyer, U., Sanders P., Sibeyn, J. (eds.) Algorithms for Memory Hierarchies. LNCS, vol. 2625, pp.\u00a0193\u2013212. Springer, Berlin (2003)"},{"key":"9394_CR31","unstructured":"Ladner, R.E., Fix, J.D., LaMarca, A.: Cache performance analysis of traversals and random accesses. In: Proc. of the Tenth Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 613\u2013622 (1999)"},{"key":"9394_CR32","series-title":"LNCS","first-page":"78","volume-title":"Algorithm Design to Robust and Efficient Software","author":"R. Ladner","year":"2002","unstructured":"Ladner, R., Fortna, R., Nguyen, B.-H.: A comparison of cache aware and cache oblivious static search trees using program instrumentation. In: Algorithm Design to Robust and Efficient Software. LNCS, vol. 2547, pp. 78\u201392. Springer, Berlin (2002)"},{"issue":"1","key":"9394_CR33","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/jagm.1998.0985","volume":"31","author":"A. LaMarca","year":"1999","unstructured":"LaMarca, A., Ladner, R.E.: The influence of caches on the performance of sorting. J. Algorithms 31(1), 66\u2013104 (1999). An earlier version appear in SODA 97","journal-title":"J. Algorithms"},{"key":"9394_CR34","unstructured":"Prokop, H.: Cache oblivious algorithms. Master\u2019s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, June 1999"},{"key":"9394_CR35","doi-asserted-by":"crossref","unstructured":"Rahman, N., Cole, R., Raman, R.: Optimised predecessor data structures for internal memory. In: Proc. 5th Int. Workshop on Algorithm Engineering (WAE), vol. 2141, pp. 67\u201378 (2001)","DOI":"10.1007\/3-540-44688-5_6"},{"issue":"3","key":"9394_CR36","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1109\/2.268881","volume":"27","author":"C. Ruemmler","year":"1994","unstructured":"Ruemmler, C., Wilkes, J.: An introduction to disk drive modeling. IEEE Computer 27(3), 17\u201329 (1994)","journal-title":"IEEE Computer"},{"key":"9394_CR37","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/BFb0030842","volume-title":"Proc. of the 1st Ann. International Conference on Computing and Combinatorics","author":"J.E. Savage","year":"1995","unstructured":"Savage, J.E.: Extending the Hong-Kung model to memory hierarchies. In: Proc. of the 1st Ann. International Conference on Computing and Combinatorics. LNCS, vol. 959, pp. 270\u2013281. Springer, Berlin (1995)"},{"issue":"6","key":"9394_CR38","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1145\/602220.602225","volume":"49","author":"S. Sen","year":"2002","unstructured":"Sen, S., Chatterjee, S., Dumir, N.: Towards a theory of cache-efficient algorithms. J. Assoc. Comput. Mach. 49(6), 828\u2013858 (2002)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"2","key":"9394_CR39","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TAU.1969.1162042","volume":"AU-17","author":"R.C. Singleton","year":"1969","unstructured":"Singleton, R.C.: An algorithm for computing the mixed radix Fast Fourier Transform. IEEE Trans. Audio Electroacoust. AU-17(2), 93\u2013103 (1969)","journal-title":"IEEE Trans. Audio Electroacoust."},{"key":"9394_CR40","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time. In: Proc. of the 16th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 75\u201384 (1975)","DOI":"10.1109\/SFCS.1975.26"},{"issue":"3","key":"9394_CR41","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett. 6(3), 80\u201382 (1977)","journal-title":"Inf. Process. Lett."},{"key":"9394_CR42","doi-asserted-by":"crossref","unstructured":"Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. 33(2) (2001)","DOI":"10.1145\/384192.384193"},{"issue":"2\u20133","key":"9394_CR43","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"J.S. Vitter","year":"1994","unstructured":"Vitter, J.S., Shriver, E.A.M.: Algorithms for parallel memory I: Two-level memories. Algorithmica 12(2\u20133), 110\u2013147 (1994)","journal-title":"Algorithmica"},{"issue":"2\u20133","key":"9394_CR44","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01185208","volume":"12","author":"J.S. Vitter","year":"1994","unstructured":"Vitter, J.S., Shriver, E.A.M.: Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica 12(2\u20133), 148\u2013169 (1994)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9394-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9394-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9394-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T02:00:16Z","timestamp":1739930416000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9394-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,9]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["9394"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9394-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3,9]]}}}