{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:25:45Z","timestamp":1726406745978},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540275800"},{"type":"electronic","value":"9783540316916"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11523468_47","type":"book-chapter","created":{"date-parts":[[2010,7,18]],"date-time":"2010-07-18T14:58:59Z","timestamp":1279465139000},"page":"576-588","source":"Crossref","is-referenced-by-count":13,"title":["Cache-Aware and Cache-Oblivious Adaptive Sorting"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Fagerberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Moruz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"47_CR1","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"},{"key":"47_CR2","unstructured":"Arge, L.: External memory data structures. In: Abello, J., Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Massive Data Sets"},{"key":"47_CR3","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":"47_CR4","doi-asserted-by":"crossref","unstructured":"Arge, L., Knudsen, M., Larsen, K.: A general lower bound on the I\/O-complexity of comparison-based algorithms. In: Proc. of Workshop on Algorithms and Data Structures (1993)","DOI":"10.1007\/3-540-57155-8_238"},{"key":"47_CR5","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. J.\u00a0Comput. Syst. Sci.\u00a07, 448\u2013461 (1973)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"47_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-540-27810-8_2","volume-title":"Algorithm Theory - SWAT 2004","author":"G.S. Brodal","year":"2004","unstructured":"Brodal, G.S.: Cache-oblivious algorithms and data structures. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 3\u201313. Springer, Heidelberg (2004)"},{"key":"47_CR7","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-45465-9_37","volume-title":"Proc. 29th International Colloquium on Automata, Languages, and Programming","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, pp. 426\u2013438. Springer, Berlin (2002)"},{"key":"47_CR8","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R.: On the limits of cache-obliviousness. In: Proc. 35th Annual ACM Symposium on Theory of Computing, pp. 307\u2013315 (2003)","DOI":"10.1145\/780542.780589"},{"key":"47_CR9","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"47_CR10","unstructured":"Demaine, E.: Cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets (2002)"},{"issue":"1","key":"47_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0890-5401(89)90050-3","volume":"83","author":"V. Estivill-Castro","year":"1989","unstructured":"Estivill-Castro, V., Wood, D.: A new measure of presortedness. Information and Computation\u00a083(1), 111\u2013119 (1989)","journal-title":"Information and Computation"},{"key":"47_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54029-6_153","volume-title":"Advances in Computing and Information - ICCI \u201991","author":"V. Estivill-Castro","year":"1991","unstructured":"Estivill-Castro, V., Wood, D.: Practical adaptive sorting. In: Dehne, F., Fiala, F., Koczkodaj, W.W. (eds.) ICCI 1991. LNCS, vol.\u00a0497, pp. 47\u201354. Springer, Heidelberg (1991)"},{"issue":"4","key":"47_CR13","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1145\/146370.146381","volume":"24","author":"V. Estivill-Castro","year":"1992","unstructured":"Estivill-Castro, V., Wood, D.: A survey of adaptive sorting algorithms. ACM Computing Surverys\u00a024(4), 441\u2013475 (1992)","journal-title":"ACM Computing Surverys"},{"key":"47_CR14","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache oblivious algorithms. In: 40th Ann. IEEE Symp. on Foundations of Computer Science, pp. 285\u2013298 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"47_CR15","doi-asserted-by":"crossref","unstructured":"Guibas, L.J., McCreight, E.M., Plass, M.F., Roberts, J.R.: A new representation of linear lists. In: Proc. 9th Ann. ACM Symp. on Theory of Computing, pp. 49\u201360 (1977)","DOI":"10.1145\/800105.803395"},{"key":"47_CR16","volume-title":"The Art of Computer Programming. Vol 3, Sorting and searching","author":"D.E. Knuth","year":"1973","unstructured":"Knuth, D.E.: The Art of Computer Programming. Vol 3, Sorting and searching. Addison-Wesley, Reading (1973)"},{"issue":"1","key":"47_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0020-0190(91)90181-G","volume":"39","author":"C. Levcopoulos","year":"1991","unstructured":"Levcopoulos, C., Petersson, O.: Splitsort \u2013 an adaptive sorting algorithm. Information Processing Letters\u00a039(1), 205\u2013211 (1991)","journal-title":"Information Processing Letters"},{"key":"47_CR18","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1109\/TC.1985.5009382","volume":"34","author":"H. Manilla","year":"1985","unstructured":"Manilla, H.: Measures of presortedness and optimal sorting algorithms. IEEE Trans. Comput.\u00a034, 318\u2013325 (1985)","journal-title":"IEEE Trans. Comput."},{"key":"47_CR19","volume-title":"Sorting and searching","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data structures and algorithms. In: Sorting and searching, vol.\u00a01. Springer, Heidelberg (1984)"},{"key":"47_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1007\/978-3-540-30140-0_50","volume-title":"Algorithms \u2013 ESA 2004","author":"A. Pagh","year":"2004","unstructured":"Pagh, A., Pagh, R., Thorup, M.: On adaptive integer sorting. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 556\u2013567. Springer, Heidelberg (2004)"},{"issue":"2","key":"47_CR21","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"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11523468_47.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:47:01Z","timestamp":1619491621000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11523468_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540275800","9783540316916"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11523468_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}