{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T15:22:29Z","timestamp":1778167349077,"version":"3.51.4"},"publisher-location":"New York, NY","reference-count":37,"publisher":"Springer New York","isbn-type":[{"value":"9781493928637","type":"print"},{"value":"9781493928644","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_62","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T19:32:23Z","timestamp":1553110343000},"page":"264-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Cache-Oblivious Model"],"prefix":"10.1007","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"61_CR334","doi-asserted-by":"crossref","unstructured":"Adams MD, Wise DS (2006) Seven at one stroke: results from a cache-oblivious paradigm for scalable matrix algorithms. In: Proceedings of the 2006 workshop on memory system performance and correctness, San Jose, pp\u00a041\u201350","DOI":"10.1145\/1178597.1178604"},{"key":"61_CR335","doi-asserted-by":"crossref","unstructured":"Afshani P, Zeh N (2011) Improved space bounds for cache-oblivious range reporting. In: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, San Francisco, pp\u00a01745\u20131758","DOI":"10.1137\/1.9781611973082.134"},{"issue":"9","key":"61_CR336","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal A, Vitter JS (1988) The Input\/Output complexity of sorting and related problems. Commun ACM 31(9):1116\u20131127","journal-title":"Commun ACM"},{"key":"61_CR337","unstructured":"Allulli L, Lichodzijewski P, Zeh N (2007) A faster cache-oblivious shortest-path algorithm for undirected graphs with bounded edge lengths. In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms, New Orleans, pp\u00a0910\u2013919"},{"key":"61_CR338","doi-asserted-by":"publisher","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 (2002) External memory data structures. In: Abello J, Pardalos PM, Resende MGC (eds) Handbook of massive data sets. Kluwer Academic, Dordrecht\/Boston\/London, pp\u00a0313\u2013358"},{"key":"61_CR339","volume-title":"Handbook on data structures and applications","author":"L Arge","year":"2005","unstructured":"Arge L, Brodal GS, Fagerberg R (2005) Cache-oblivious data structures. In: Mehta D, Sahni S (eds) Handbook on data structures and applications. Chapman & Hall\/CRC, Boca Raton\/London\/New York\/Washington, D.C"},{"key":"61_CR340","doi-asserted-by":"crossref","unstructured":"Arge L, Bender MA, Demaine ED, Holland-Minkley B, Munro JI (2007) An optimal cache-oblivious priority queue and its application to graph algorithms. SIAM J Comput 36(6):1672\u20131695. Conference version appeared at STOC 2002","DOI":"10.1137\/S0097539703428324"},{"key":"61_CR341","doi-asserted-by":"crossref","unstructured":"Arge L, M\u00f8lhave T, Zeh N (2008) Cache-oblivious red-blue line segment intersection. In: Proceedings of the 16th annual European symposium on algorithms, Karlsruhe. LNCS, vol\u00a05193, pp\u00a088\u201399","DOI":"10.1007\/978-3-540-87744-8_8"},{"key":"61_CR342","doi-asserted-by":"crossref","unstructured":"Bender M, Cole R, Demaine E, Farach-Colton M (2002) Scanning and traversing: maintaining data for traversals in a memory hierarchy. In: Proceedings of the 10th annual European symposium on algorithms, Rome. LNCS, vol\u00a02461, pp\u00a0139\u2013151","DOI":"10.1007\/3-540-45749-6_16"},{"key":"61_CR343","doi-asserted-by":"crossref","unstructured":"Bender M, Cole R, Raman R (2002) Exponential structures for cache-oblivious algorithms. In: Proceedings of the 29th international colloquium on automata, languages, and programming, M\u00e1laga. LNCS, vol\u00a02380, pp\u00a0195\u2013207","DOI":"10.1007\/3-540-45465-9_18"},{"key":"61_CR344","doi-asserted-by":"crossref","unstructured":"Bender M, Demaine E, Farach-Colton M (2002) Efficient tree layout in a multilevel memory hierarchy. In: Proceedings of the 10th annual European symposium on algorithms, Rome. LNCS, vol\u00a02461, pp\u00a0165\u2013173, corrected full version at \n                  http:\/\/arxiv.org\/abs\/cs\/0211010","DOI":"10.1007\/3-540-45749-6_18"},{"key":"61_CR345","doi-asserted-by":"crossref","unstructured":"Bender MA, Demaine ED, Farach-Colton M (2005) Cache-oblivious B-trees. SIAM J Comput 35(2):341\u2013358. Conference version appeared at FOCS 2000","DOI":"10.1137\/S0097539701389956"},{"key":"61_CR346","doi-asserted-by":"crossref","unstructured":"Bender MA, Brodal GS, Fagerberg R, Ge D, He S, Hu H, Iacono J, L\u00f3pez-Ortiz A (2011) The cost of cache-oblivious searching. Algorithmica 61(2):463\u2013505. Conference version appeared at FOCS 2003","DOI":"10.1007\/s00453-010-9394-0"},{"key":"61_CR347","doi-asserted-by":"crossref","unstructured":"Bille P, St\u00f6ckel M (2012) Fast and cache-oblivious dynamic programming with local dependencies. In: Proceedings of the 6th international conference on language and automata theory and applications, A Coru\u00f1a. LNCS, vol\u00a07183, pp\u00a0131\u2013142","DOI":"10.1007\/978-3-642-28332-1_12"},{"key":"61_CR348","doi-asserted-by":"crossref","unstructured":"Brodal GS (2004) Cache-oblivious algorithms and data structures. In: Proceedings of the 9th Scandinavian workshop on algorithm theory, Humleb\u00e6k. LNCS, vol\u00a03111, pp\u00a03\u201313","DOI":"10.1007\/978-3-540-27810-8_2"},{"key":"61_CR349","doi-asserted-by":"crossref","unstructured":"Brodal GS, Fagerberg R (2002) Cache oblivious distribution sweeping. In: Proceedings of the 29th international colloquium on automata, languages, and programming, M\u00e1laga. LNCS, vol\u00a02380, pp\u00a0426\u2013438","DOI":"10.1007\/3-540-45465-9_37"},{"key":"61_CR350","unstructured":"Brodal GS, Fagerberg R (2002) Funnel heap \u2013 a cache oblivious priority queue. In: Proceedings of the 13th international symposium on algorithms and computation, Vancouver. LNCS, vol 2518, pp\u00a0219\u2013228"},{"key":"61_CR351","doi-asserted-by":"crossref","unstructured":"Brodal GS, Fagerberg R (2003) On the limits of cache-obliviousness. In: Proceedings of the 35th annual ACM symposium on theory of computing, San Diego, pp\u00a0307\u2013315","DOI":"10.1145\/780542.780589"},{"key":"61_CR352","doi-asserted-by":"crossref","unstructured":"Brodal GS, Fagerberg R, Meyer U, Zeh N (2004) Cache-oblivious data structures and algorithms for undirected breadth-first search and shortest paths. In: Proceedings of the 9th Scandinavian workshop on algorithm theory, Humleb\u00e6k. LNCS, vol 3111, pp\u00a0480\u2013492","DOI":"10.1007\/978-3-540-27810-8_41"},{"key":"61_CR353","doi-asserted-by":"crossref","unstructured":"Brodal GS, Fagerberg R, Moruz G (2005) Cache-aware and cache-oblivious adaptive sorting. In: Proceedings of the 32nd international colloquium on automata, languages and programming, Lisbon. LNCS, vol\u00a03580, pp\u00a0576\u2013588","DOI":"10.1007\/11523468_47"},{"key":"61_CR354","unstructured":"Brodal GS, Fagerberg R, Vinther K (2007) Engineering a cache-oblivious sorting algorithm. ACM J Exp Algorithmics 12:Article 2.2. Conference version appeared at ALENEX 2004"},{"issue":"8","key":"61_CR355","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1016\/j.comgeo.2010.04.005","volume":"43","author":"TM Chan","year":"2010","unstructured":"Chan TM, Chen EY (2010) Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection. Comput Geom 43(8):636\u2013646","journal-title":"Comput Geom"},{"key":"61_CR356","doi-asserted-by":"crossref","unstructured":"Chowdhury RA, Ramachandran V (2004) Cache-oblivious shortest paths in graphs using buffer heap. In: Proceedings of the 16th annual ACM symposium on parallelism in algorithms and architectures, Barcelona","DOI":"10.1145\/1007912.1007949"},{"key":"61_CR357","doi-asserted-by":"crossref","unstructured":"Chowdhury RA, Ramachandran V (2006) Cache-oblivious dynamic programming. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms, Miami, pp\u00a0591\u2013600","DOI":"10.1145\/1109557.1109622"},{"issue":"3","key":"61_CR358","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1109\/TCBB.2008.94","volume":"7","author":"RA Chowdhury","year":"2010","unstructured":"Chowdhury RA, Le HS, Ramachandran V (2010) Cache-oblivious dynamic programming for bioinformatics. IEEE\/ACM Trans Comput Biol Bioinf 7(3):495\u2013510","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"61_CR359","unstructured":"Demaine ED (2002) Cache-oblivious algorithms and data structures. Lecture notes from the EEF summer school on massive data sets. Online version at \n                  http:\/\/theory.csail.mit.edu\/~edemaine\/papers\/BRICS2002\/"},{"key":"61_CR360","doi-asserted-by":"crossref","unstructured":"Fagerberg R, Pagh A, Pagh R (2006) External string sorting: faster and cache-oblivious. In: Proceedings of the 23rd annual symposium on theoretical aspects of computer science, Marseille. LNCS, vol\u00a03884, pp\u00a068\u201379","DOI":"10.1007\/11672142_4"},{"key":"61_CR361","doi-asserted-by":"crossref","unstructured":"Farzan A, Ferragina P, Franceschini G, Munro JI (2005) Cache-oblivious comparison-based algorithms on multisets. In: Proceedings of the 13th annual European symposium on algorithms, Palma de Mallorca. LNCS, vol\u00a03669, pp\u00a0305\u2013316","DOI":"10.1007\/11561071_29"},{"key":"61_CR362","unstructured":"Franceschini G (2004) Proximity mergesort: optimal in-place sorting in the cache-oblivious model. In: Proceedings of the 15th annual ACM-SIAM symposium on discrete algorithms, New Orleans, pp\u00a0291\u2013299"},{"key":"61_CR363","doi-asserted-by":"crossref","unstructured":"Frigo M, Leiserson CE, Prokop H, Ramachandran S (2012) Cache-oblivious algorithms. ACM Trans Algorithms 8(1):4. Conference version appeared at FOCS 1999","DOI":"10.1145\/2071379.2071383"},{"key":"61_CR364","doi-asserted-by":"crossref","unstructured":"Jampala H, Zeh N (2005) Cache-oblivious planar shortest paths. In: Proceedings of the 32nd international colloquium on automata, languages, and programming, Lisbon. LNCS, vol\u00a03580, pp\u00a0563\u2013575","DOI":"10.1007\/11523468_46"},{"key":"61_CR365","series-title":"LNCS","volume-title":"Algorithms for memory hierarchies","year":"2003","unstructured":"Meyer U, Sanders P, Sibeyn JF (eds) (2003) Algorithms for memory hierarchies. LNCS, vol\u00a02625. Springer, Berlin\/Heidelberg\/New York"},{"key":"61_CR366","volume-title":"Cache-oblivious algorithms","author":"H Prokop","year":"1999","unstructured":"Prokop H (1999) Cache-oblivious algorithms. Master\u2019s thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology"},{"issue":"2","key":"61_CR367","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"JS Vitter","year":"2001","unstructured":"Vitter JS (2001) External memory algorithms and data structures: dealing with MASSIVE data. ACM Comput Surv 33(2):209\u2013271","journal-title":"ACM Comput Surv"},{"key":"61_CR368","volume-title":"Handbook on data structures and applications","author":"JS Vitter","year":"2005","unstructured":"Vitter JS (2005) Geometric and spatial data structures in external memory. In: Mehta D, Sahni S (eds) Handbook on data structures and applications. Chapman & Hall\/CRC, Boca Raton\/London\/New York\/Washington, D.C"},{"issue":"4","key":"61_CR369","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1561\/0400000014","volume":"2","author":"JS Vitter","year":"2008","unstructured":"Vitter JS (2008) Algorithms and data structures for external memory. Found Trends Theor Comput Sci 2(4):305\u2013474","journal-title":"Found Trends Theor Comput Sci"},{"key":"61_CR370","doi-asserted-by":"crossref","unstructured":"Yotov K, Roeder T, Pingali K, Gunnels JA, Gustavson FG (2007) An experimental comparison of cache-oblivious and cache-conscious programs. In: Proceedings of the 19th annual ACM symposium on parallelism in algorithms and architectures, San Diego, pp\u00a093\u2013104","DOI":"10.1145\/1248377.1248394"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_62","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T20:24:42Z","timestamp":1553113482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_62","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}