{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T19:38:57Z","timestamp":1773776337554,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":73,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540223399","type":"print"},{"value":"9783540278108","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_2","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"3-13","source":"Crossref","is-referenced-by-count":19,"title":["Cache-Oblivious Algorithms and Data Structures"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s00453-001-0088-5","volume":"32","author":"J. Abello","year":"2002","unstructured":"Abello, J., Buchsbaum, A.L., Westbrook, J.R.: A functional approach to external graph algorithms. Algorithmica\u00a032(3), 437\u2013458 (2002)","journal-title":"Algorithmica"},{"key":"2_CR2","first-page":"237","volume-title":"Proc. 19th ACM Symposium on Computational Geometry","author":"P. Agarwal","year":"2003","unstructured":"Agarwal, P., Arge, L., Danner, A., Holland-Minkley, B.: Cache-oblivious data structures for orthogonal range searching. In: Proc. 19th ACM Symposium on Computational Geometry, pp. 237\u2013245. ACM Press, New York (2003)"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Alpern, B., Chandra, A.K., Snir, M.: A model for hierarchical memory. In: Proc. 19th Annual ACM Symposium on Theory of Computing, pp. 305\u2013314. AMC Press (1987)","DOI":"10.1145\/28395.28428"},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1145\/62212.62227","volume-title":"Proc. 20th Annual ACM symposium on Theory of computing","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Chandra, A.: Virtual memory algorithms. In: Proc. 20th Annual ACM symposium on Theory of computing, pp. 173\u2013185. ACM Press, New York (1988)"},{"key":"2_CR5","first-page":"204","volume-title":"Proc. 28th Annual IEEE Symposium on Foundations of Computer Science","author":"A. Aggarwal","year":"1987","unstructured":"Aggarwal, A., Chandra, A.K., Snir, M.: Hierarchical memory with block transfer. In: Proc. 28th Annual IEEE Symposium on Foundations of Computer Science, pp. 204\u2013216. IEEE Computer Society Press, Los Alamitos (1987)"},{"issue":"9","key":"2_CR6","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. Communications of the ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Communications of the ACM"},{"issue":"2\u20133","key":"2_CR7","doi-asserted-by":"publisher","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\u00a012(2\u20133), 72\u2013109 (1994)","journal-title":"Algorithmica"},{"key":"2_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-52846-6_82","volume-title":"SWAT \u201990","author":"A. Andersson","year":"1990","unstructured":"Andersson, A., Lai, T.W.: Fast updating of well-balanced trees. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 111\u2013121. Springer, Heidelberg (1990)"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-1-4615-0005-6_9","volume-title":"Handbook of Massive Data Sets","author":"L. Arge","year":"2002","unstructured":"Arge, L.: External memory data structures. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets, pp. 313\u2013358. Kluwer Academic Publishers, Dordrecht (2002)"},{"issue":"1","key":"2_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-003-1021-x","volume":"37","author":"L. Arge","year":"2003","unstructured":"Arge, L.: The buffer tree: A technique for designing batched external data structures. Algorithmica\u00a037(1), 1\u201324 (2003)","journal-title":"Algorithmica"},{"key":"2_CR11","first-page":"268","volume-title":"Proc. 34th Annual ACM Symposium on Theory of Computing","author":"L. Arge","year":"2002","unstructured":"Arge, L., Bender, M.A., Demaine, E.D., Holland-Minkley, B., Munro, J.I.: Cache-oblivious priority queue and graph algorithm applications. In: Proc. 34th Annual ACM Symposium on Theory of Computing, pp. 268\u2013276. ACM Press, New York (2002)"},{"key":"2_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-44985-X_37","volume-title":"Algorithm Theory - SWAT 2000","author":"L. Arge","year":"2000","unstructured":"Arge, L., Brodal, G., Toma, L.: On external-memory MST, SSSP, and multi-way planar graph separation (Extended abstract). In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 433\u2013447. Springer, Heidelberg (2000)"},{"key":"2_CR13","first-page":"27","volume-title":"Handbook of Data Structures and Applications","author":"L. Arge","year":"2004","unstructured":"Arge, L., Brodal, G.S., Fagerberg, R.: Cache-oblivious data structures. In: Mehta, D., Sahni, S. (eds.) Handbook of Data Structures and Applications, p. 27. CRC Press, Boca Raton (2004)"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Arge, L., Chase, J., Vitter, J., Wickremesinghe, R.: Efficient sorting using registers and caches. ACM Journal of Experimental Algorithmics\u00a07(9) (2002)","DOI":"10.1145\/944618.944627"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/3-540-57155-8_238","volume-title":"Algorithms and Data Structures","author":"L. Arge","year":"1993","unstructured":"Arge, L., Knudsen, M., Larsen, K.: A general lower bound on the I\/Ocomplexity of comparison-based algorithms. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 83\u201394. Springer, Heidelberg (1993)"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Arge, L., Chase, J., Vitter, J., Wickremesinghe, R.: Efficient sorting using registers and caches. ACM Journal of Experimental Algorithmics\u00a07(9) (2002)","DOI":"10.1145\/944618.944627"},{"key":"2_CR17","doi-asserted-by":"publisher","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 Informatica\u00a01, 173\u2013189 (1972)","journal-title":"Acta Informatica"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-45749-6_16","volume-title":"Algorithms - ESA 2002","author":"M. Bender","year":"2002","unstructured":"Bender, M., Cole, R., Demaine, E., Farach-Colton, M.: Scanning and traversing: Maintaining data for traversals in a memory hierarchy. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 139\u2013151. Springer, Heidelberg (2002)"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-45465-9_18","volume-title":"Automata, Languages and Programming","author":"M. Bender","year":"2002","unstructured":"Bender, M., Cole, R., Raman, R.: Exponential structures for efficient cache-oblivious algorithms. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 195\u2013207. Springer, Heidelberg (2002)"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Bender, M., Demaine, E., Farach-Colton, M.: Efficient tree layout in a multilevel memory hierarchy. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 165\u2013173. Springer, Heidelberg (2002) ,Full version at http:\/\/www.cs.sunysb.edu\/~bender\/pub\/treelayout-full.ps","DOI":"10.1007\/3-540-45749-6_18"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1109\/SFCS.2003.1238201","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., L\u00f3pez-Ortiz, A.: The cost of cache-oblivious searching. In: Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 271\u2013282. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1109\/SFCS.2000.892128","volume-title":"Proc. 41st Annual IEEE Symposium on Foundations of Computer Science","author":"M.A. Bender","year":"2000","unstructured":"Bender, M.A., Demaine, E., Farach-Colton, M.: Cache-oblivious B-trees. In: Proc. 41st Annual IEEE Symposium on Foundations of Computer Science, pp. 399\u2013409. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"2_CR23","unstructured":"Bender, M.A., Duan, Z., Iacono, J., Wu, J.: A locality-preserving cache-oblivious dynamic dictionary. In: Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 29\u201338. ACM-SIAM (2002)"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J.L. Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Communication of the ACM\u00a018, 509\u2013517 (1975)","journal-title":"Communication of the ACM"},{"issue":"5","key":"2_CR25","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J.L. Bentley","year":"1979","unstructured":"Bentley, J.L.: Decomposable searching problems. Information Processing Letters\u00a08(5), 244\u2013251 (1979)","journal-title":"Information Processing Letters"},{"key":"2_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/3-540-48224-5_11","volume-title":"Automata, Languages and Programming","author":"G. Bilardi","year":"2001","unstructured":"Bilardi, G., Peserico, E.: A characterization of temporal locality and its portability across memory hierarchies. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 128\u2013139. Springer, Heidelberg (2001)"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences\u00a07, 448\u2013461 (1973)","journal-title":"Journal of Computer and System Sciences"},{"key":"2_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-45465-9_37","volume-title":"Automata, Languages and Programming","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: Cache oblivious distribution sweeping. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 426\u2013438. Springer, Heidelberg (2002)"},{"key":"2_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/3-540-36136-7_20","volume-title":"Algorithms and Computation","author":"G.S. Brodal","year":"2002","unstructured":"Brodal, G.S., Fagerberg, R.: Funnel heap - a cache oblivious priority queue. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 219\u2013228. Springer, Heidelberg (2002)"},{"key":"2_CR30","first-page":"307","volume-title":"Proc. 35th ACM Symposium on Theory of Computing","author":"G.S. Brodal","year":"2003","unstructured":"Brodal, G.S., Fagerberg, R.: On the limits of cache-obliviousness. In: Proc. 35th ACM Symposium on Theory of Computing, pp. 307\u2013315. ACM Press, New York (2003)"},{"key":"2_CR31","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 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 39\u201348. ACM-SIAM (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"key":"2_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/978-3-540-27810-8_41","volume-title":"Algorithm Theory - SWAT 2004","author":"G.S. Brodal","year":"2004","unstructured":"Brodal, G.S., Fagerberg, R., Meyer, U., Zeh, N.: Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 480\u2013492. Springer, Heidelberg (2004)"},{"key":"2_CR33","unstructured":"Brodal, G.S., Fagerberg, R., Vinther, K.: Engineering a cache-oblivious sorting algorithm. In: Proc. 6th Workshop on Algorithm Engineering and Experiments, p. 14 (2004)"},{"key":"2_CR34","first-page":"859","volume-title":"Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Buchsbaum","year":"2000","unstructured":"Buchsbaum, A., Goldwasser, M., Venkatasubramanian, S., Westbrook, J.: On external memory graph traversal. In: Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 859\u2013860. ACM Press, New York (2000)"},{"key":"2_CR35","first-page":"444","volume-title":"Proc. 1999 Conference on Supercomputing, ACM SIGARCH","author":"S. Chatterjee","year":"1999","unstructured":"Chatterjee, S., Jain, V.V., Lebeck, A.R., Mundhra, S., Thottethodi, M.: Nonlinear array layouts for hierarchical memory systems. In: Proc. 1999 Conference on Supercomputing, ACM SIGARCH, pp. 444\u2013453. ACM Press, New York (1999)"},{"key":"2_CR36","unstructured":"Chiang, Y., Goodrich, M.T., Grove, E.F., Tamassia, R., Vengroff, D.E., Vitter, J.S.: External-memory graph algorithms. In: Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 139\u2013149. ACM-SIAM (1995)"},{"key":"2_CR37","volume-title":"Proc. 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"R.A. Chowdhury","year":"2004","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-oblivious shortest paths in graphs using buffer heap. In: Proc. 16th Annual ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, New York (2004)"},{"key":"2_CR38","series-title":"Lecture Notes in Computer Science","volume-title":"Proc. EFF summer school on massive data sets","author":"E.D. Demaine","year":"2004","unstructured":"Demaine, E.D.: Cache-oblivious data structures and algorithms. In: Proc. EFF summer school on massive data sets. LNCS, Springer, Heidelberg (2004)"},{"key":"2_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/3-540-52846-6_87","volume-title":"SWAT \u201990","author":"P.F. Dietz","year":"1990","unstructured":"Dietz, P.F., Zhang, J.: Lower bounds for monotonic list labeling. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 173\u2013180. Springer, Heidelberg (1990)"},{"key":"2_CR40","unstructured":"Farzan, A., Munro, J.I.: Cache-oblivious sorting and searching in multisets (2004) (manuscript)"},{"key":"2_CR41","unstructured":"Franceschini, G.: Proximity mergesort: optimal in-place sorting in the cacheoblivious model. In: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 291\u2013299. ACM-SIAM (2004)"},{"key":"2_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/3-540-45061-0_27","volume-title":"Automata, Languages and Programming","author":"G. Franceschini","year":"2003","unstructured":"Franceschini, G., Grossi, R.: Optimal cache-oblivious implicit dictionaries. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 316\u2013331. Springer, Heidelberg (2003)"},{"key":"2_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-540-45078-8_11","volume-title":"Algorithms and Data Structures","author":"G. Franceschini","year":"2003","unstructured":"Franceschini, G., Grossi, R.: Optimal worst-case operations for implicit cacheoblivious search trees. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 114\u2013126. Springer, Heidelberg (2003)"},{"key":"2_CR44","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-oblivious algorithms. In: 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 285\u2013297. IEEE Computer Society Press, Los Alamitos (1999)"},{"key":"2_CR45","first-page":"714","volume-title":"Proc. 34th Annual IEEE Symposium on Foundations of Computer Science","author":"M.T. Goodrich","year":"1993","unstructured":"Goodrich, M.T., Tsay, J.-J., Vengroff, D.E., Vitter, J.S.: External-memory computational geometry. In: Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, pp. 714\u2013723. IEEE Computer Society Press, Los Alamitos (1993)"},{"key":"2_CR46","volume-title":"Computer Architecture: A Quantitative Approach","author":"J.L. Hennessy","year":"2002","unstructured":"Hennessy, J.L., Patterson, D.A.: Computer Architecture: A Quantitative Approach, 3rd edn. Morgan Kaufmann, San Francisco (2002)","edition":"3"},{"key":"2_CR47","doi-asserted-by":"crossref","unstructured":"Hong, J.-W., Kung, H.T.: I\/O complexity: The red-blue pebble game. In: Proc. 13th Annual ACM Symposium on Theory of Computation, pp. 326\u2013333. AMC Press (1981)","DOI":"10.1145\/800076.802486"},{"key":"2_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/3-540-10843-2_34","volume-title":"Automata, Languages and Programming","author":"A. Itai","year":"1981","unstructured":"Itai, A., Konheim, A.G., Rodeh, M.: A sparse table implementation of priority queues. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol.\u00a0115, pp. 417\u2013431. Springer, Heidelberg (1981)"},{"key":"2_CR49","doi-asserted-by":"crossref","unstructured":"Kanth, K.V.R., Singh, A.K.: Optimal dynamic range searching in non-replicating index structures. In: Beeri, C., Bruneman, P. (eds.) ICDT 1999. LNCS, vol.\u00a01540, pp. 257\u2013276. Springer, Heidelberg (1998)","DOI":"10.1007\/3-540-49257-7_17"},{"key":"2_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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.F. (eds.) Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625, pp. 193\u2013212. Springer, Heidelberg (2003)"},{"key":"2_CR51","first-page":"169","volume-title":"Proc. 8th SPDP","author":"V. Kumar","year":"1996","unstructured":"Kumar, V., Schwabe, E.J.: Improved algorithms and data structures for solving graph problems in external memory. In: Proc. 8th SPDP, pp. 169\u2013177. IEEE Computer Society Press, Los Alamitos (1996)"},{"key":"2_CR52","unstructured":"Ladner, R.E., Fix, J.D., LaMarca, A.: Cache performance analysis of traversals and random accesses. In: Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 613\u2013622. ACM-SIAM (1999)"},{"key":"2_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/3-540-36383-1_4","volume-title":"Experimental Algorithmics","author":"R.E. Ladner","year":"2002","unstructured":"Ladner, R.E., Fortna, R., Nguyen, B.-H.: A comparison of cache aware and cache oblivious static search trees using program instrumentation. In: Fleischer, R., Moret, B.M.E., Schmidt, E.M. (eds.) Experimental Algorithmics. LNCS, vol.\u00a02547, pp. 78\u201392. Springer, Heidelberg (2002)"},{"key":"2_CR54","doi-asserted-by":"crossref","unstructured":"LaMarca, A., Ladner, R.E.: The influence of caches on the performance of heaps. ACM Journal of Experimental Algorithms\u00a01(4) (1996)","DOI":"10.1145\/235141.235145"},{"key":"2_CR55","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a031, 66\u2013104 (1999)","journal-title":"Journal of Algorithms"},{"key":"2_CR56","doi-asserted-by":"crossref","unstructured":"LaMarca, A., Ladner, R.E.: The influence of caches on the performance of heaps. ACM Journal of Experimental Algorithms\u00a01(4) (1996)","DOI":"10.1145\/235141.235145"},{"key":"2_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36574-5","volume-title":"Algorithms for Memory Hierarchies","author":"U. Meyer","year":"2003","unstructured":"Meyer, U., Sanders, P., Sibeyn, J.F.: Algorithms for Memory Hierarchies. LNCS, vol.\u00a02625. Springer, Heidelberg (2003)"},{"key":"2_CR58","unstructured":"Munagala, K., Ranade, A.: I\/O-complexity of graph algorithms. In: Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 687\u2013694. ACMSIAM (1999)"},{"key":"2_CR59","unstructured":"Ohashi, D.: Cache oblivious data structures. Master\u2019s thesis, Department of Computer Science, University of Waterloo, Waterloo, Canada (2000)"},{"key":"2_CR60","unstructured":"Prokop, H.: Cache-oblivious algorithms. Master\u2019s thesis, Massachusetts Institute of Technology (June 1999)"},{"key":"2_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-44688-5_6","volume-title":"Algorithm Engineering","author":"N. Rahman","year":"2001","unstructured":"Rahman, N., Cole, R., Raman, R.: Optimised predecessor data structures for internal memory. In: Brodal, G.S., Frigioni, D., Marchetti-Spaccamela, A. (eds.) WAE 2001. LNCS, vol.\u00a02141, pp. 67\u201378. Springer, Heidelberg (2001)"},{"key":"2_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/BFb0030842","volume-title":"Computing and Combinatorics","author":"J.E. Savage","year":"1995","unstructured":"Savage, J.E.: Extending the Hong-Kung model to memory hierachies. In: Li, M., Du, D.-Z. (eds.) COCOON 1995. LNCS, vol.\u00a0959, pp. 270\u2013281. Springer, Heidelberg (1995)"},{"key":"2_CR63","unstructured":"Sen, S., Chatterjee, S.: Towards a theory of cache-efficient algorithms. In: Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 829\u2013838. ACM-SIAM (2000)"},{"key":"2_CR64","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized Efficiency of List Update and Paging Rules. Communications of the ACM\u00a028, 202\u2013208 (1985)","journal-title":"Communications of the ACM"},{"key":"2_CR65","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik\u00a013, 354\u2013356 (1969)","journal-title":"Numerische Mathematik"},{"issue":"4","key":"2_CR66","doi-asserted-by":"publisher","first-page":"1065","DOI":"10.1137\/S0895479896297744","volume":"18","author":"S. Toledo","year":"1997","unstructured":"Toledo, S.: Locality of reference in LU decomposition with partial pivoting. SIAM Journal on Matrix Analysis and Applications,\u00a018(4), 1065\u20131081 (1997)","journal-title":"SIAM Journal on Matrix Analysis and Applications,"},{"key":"2_CR67","doi-asserted-by":"publisher","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. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"key":"2_CR68","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory\u00a010, 99\u2013127 (1977)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"2_CR69","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys\u00a033(2), 209\u2013271 (2001)","journal-title":"ACM Computing Surveys"},{"issue":"2\u20133","key":"2_CR70","doi-asserted-by":"publisher","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\u00a012(2\u20133), 110\u2013147 (1994)","journal-title":"Algorithmica"},{"issue":"2\u20133","key":"2_CR71","doi-asserted-by":"publisher","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\u00a012(2\u20133), 148\u2013169 (1994)","journal-title":"Algorithmica"},{"issue":"2","key":"2_CR72","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0890-5401(92)90034-D","volume":"97","author":"D.E. Willard","year":"1992","unstructured":"Willard, D.E.: A density control algorithm for doing insertions and deletions in a sequentially ordered file in good worst-case time. Information and Computation\u00a097(2), 150\u2013204 (1992)","journal-title":"Information and Computation"},{"key":"2_CR73","doi-asserted-by":"crossref","unstructured":"Xiao, L., Zhang, X., Kubricht, S.A.: Improving memory performance of sorting algorithms. ACM Journal of Experimental Algorithmics\u00a05(3) (2000)","DOI":"10.1145\/351827.384245"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T21:51:53Z","timestamp":1740261113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":73,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}