{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:15:44Z","timestamp":1725470144069},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_63","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"708-719","source":"Crossref","is-referenced-by-count":5,"title":["Skewed Binary Search Trees"],"prefix":"10.1007","author":[{"given":"Gerth St\u00f8lting","family":"Brodal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriel","family":"Moruz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"63_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":"63_CR2","doi-asserted-by":"crossref","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 (2003) (manuscript)","DOI":"10.1007\/3-540-45749-6_18"},{"key":"63_CR3","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)"},{"key":"63_CR4","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":"63_CR5","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF00288683","volume":"1","author":"R. Bayer","year":"1972","unstructured":"Bayer, R., McCreight, E.M.: Organization and maintenance of large ordered indices. Acta Informatica\u00a01, 173\u2013189 (1972)","journal-title":"Acta Informatica"},{"key":"63_CR6","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. In: Proc. 41st Annual Symposium on Foundations of Computer Science, pp. 399\u2013409 (2000)","DOI":"10.1109\/SFCS.2000.892128"},{"key":"63_CR7","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 (2002)"},{"key":"63_CR8","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":"63_CR9","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 (2002)","DOI":"10.7146\/brics.v8i36.21696"},{"key":"63_CR10","unstructured":"Brodal, G.S., Fagerberg, R., Moruz, G.: On the adaptiveness of quicksort. In: Proc. 7th Workshop on Algorithm Engineering and Experiments, pp. 130\u2013140 (2005)"},{"key":"63_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/11534273_34","volume-title":"Algorithms and Data Structures","author":"G.S. Brodal","year":"2005","unstructured":"Brodal, G.S., Moruz, G.: Tradeoffs between branch mispredictions and comparisons for sorting algorithms. In: Dehne, F., L\u00f3pez-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol.\u00a03608, pp. 385\u2013395. Springer, Heidelberg (2005)"},{"key":"63_CR12","unstructured":"Demaine, E.D., Iacono, J., Langerman, S.: Worst-case optimal tree layout in a memory hierarchy (August 2004) (manuscript)"},{"key":"63_CR13","doi-asserted-by":"crossref","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\u2013298 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"issue":"2","key":"63_CR14","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jagm.1999.1014","volume":"32","author":"J. Gil","year":"1999","unstructured":"Gil, J., Itai, A.: How to pack trees. Journal of Algorithms\u00a032(2), 108\u2013132 (1999)","journal-title":"Journal of Algorithms"},{"key":"63_CR15","doi-asserted-by":"crossref","unstructured":"Nievergelt, J., Reingold, E.M.: Binary search trees of bounded balance. In: Proc. 4th Annual ACM Symposium on Theory of Computing, pp. 137\u2013142 (1972)","DOI":"10.1145\/800152.804906"},{"key":"63_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1007\/978-3-540-30140-0_69","volume-title":"Algorithms \u2013 ESA 2004","author":"P. Sanders","year":"2004","unstructured":"Sanders, P., Winkel, S.: Super scalar sample sort. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 784\u2013796. Springer, Heidelberg (2004)"},{"issue":"2","key":"63_CR17","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","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_63.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:37Z","timestamp":1605642037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11841036_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}