{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T04:46:23Z","timestamp":1746679583801},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385261"},{"type":"electronic","value":"9783642385278"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38527-8_13","type":"book-chapter","created":{"date-parts":[[2013,5,8]],"date-time":"2013-05-08T13:23:02Z","timestamp":1368019382000},"page":"127-138","source":"Crossref","is-referenced-by-count":4,"title":["Branchless Search Programs"],"prefix":"10.1007","author":[{"given":"Amr","family":"Elmasry","sequence":"first","affiliation":[]},{"given":"Jyrki","family":"Katajainen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"10","key":"13_CR1","doi-asserted-by":"publisher","first-page":"1125","DOI":"10.1002\/spe.4380211009","volume":"21","author":"A. Andersson","year":"1991","unstructured":"Andersson, A.: A note on searching in a binary search tree. Software Pract. Exper.\u00a021(10), 1125\u20131128 (1991)","journal-title":"Software Pract. Exper."},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/3-540-45749-6_18","volume-title":"Algorithms - ESA 2002","author":"M.A. Bender","year":"2002","unstructured":"Bender, M.A., Demaine, E.D., 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)"},{"key":"13_CR3","volume-title":"Programming Pearls","author":"J. Bentley","year":"2000","unstructured":"Bentley, J.: Programming Pearls, 2nd edn. Addison-Wesley, Reading (2000)","edition":"2"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1007\/11841036_63","volume-title":"Algorithms \u2013 ESA 2006","author":"G.S. Brodal","year":"2006","unstructured":"Brodal, G.S., Moruz, G.: Skewed binary search trees. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 708\u2013719. Springer, Heidelberg (2006)"},{"key":"13_CR5","first-page":"157","volume-title":"SIGMOD 2002","author":"S. Chen","year":"2002","unstructured":"Chen, S., Gibbons, P.B., Mowry, T.C., Valentin, G.: Fractal prefetching B\u2009+\u2009-trees: Optimizing both cache and disk performance. In: SIGMOD 2002, pp. 157\u2013168. ACM, New York (2002)"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-30347-0_14","volume-title":"Fun with Algorithms","author":"A. Elmasry","year":"2012","unstructured":"Elmasry, A., Katajainen, J.: Lean programs, branch mispredictions, and sorting. In: Kranakis, E., Krizanc, D., Luccio, F. (eds.) FUN 2012. LNCS, vol.\u00a07288, pp. 119\u2013130. Springer, Heidelberg (2012)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-30850-5_15","volume-title":"Experimental Algorithms","author":"A. Elmasry","year":"2012","unstructured":"Elmasry, A., Katajainen, J., Stenmark, M.: Branch mispredictions don\u2019t affect mergesort. In: Klasing, R. (ed.) SEA 2012. LNCS, vol.\u00a07276, pp. 160\u2013171. Springer, Heidelberg (2012)"},{"key":"13_CR8","first-page":"8","volume-title":"FOCS 1978","author":"L.J. Guibas","year":"1978","unstructured":"Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. In: FOCS 1978, pp. 8\u201321. IEEE Computer Society, Los Alamitos (1978)"},{"unstructured":"Jensen, C., Katajainen, J., Vitale, F.: Experimental evaluation of local heaps. CPH STL Report 2006-1, Department of Computer Science, University of Copenhagen, Copenhagen (2006)","key":"13_CR9"},{"issue":"3","key":"13_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(75)90001-0","volume":"4","author":"D.B. Johnson","year":"1975","unstructured":"Johnson, D.B.: Priority queues with update and finding minimum spanning trees. Inform. Process. Lett.\u00a04(3), 53\u201357 (1975)","journal-title":"Inform. Process. Lett."},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1007\/11841036_69","volume-title":"Algorithms \u2013 ESA 2006","author":"K. Kaligosi","year":"2006","unstructured":"Kaligosi, K., Sanders, P.: How branch mispredictions affect quicksort. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 780\u2013791. Springer, Heidelberg (2006)"},{"unstructured":"Katajainen, J.: Branchless search programs: Electronic appendix. CPH STL Report 2012-1, Department of Computer Science, University of Copenhagen, Copenhagen (2012)","key":"13_CR12"},{"key":"13_CR13","volume-title":"Sorting and Searching, The Art of Computer Programming","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, The Art of Computer Programming, 2nd edn., vol.\u00a03. Addison-Wesley, Reading (1998)","edition":"2"},{"key":"13_CR14","first-page":"679","volume-title":"5th Hellenic Conference on Informatics","author":"K. Oksanen","year":"1995","unstructured":"Oksanen, K., Malmi, L.: Memory reference locality and periodic relocation in main memory search trees. In: 5th Hellenic Conference on Informatics, pp. 679\u2013687. Greek Computer Society, Athens (1995)"},{"unstructured":"Patterson, D.A., Hennessy, J.L.: Computer Organization and Design: The Hardware\/Software Interface, revised 4th edn. Morgan Kaufmann, Waltham (2012)","key":"13_CR15"},{"unstructured":"Prokop, H.: Cache-oblivious algorithms. Master\u2019s Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge (1999)","key":"13_CR16"},{"key":"13_CR17","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":"13_CR18","series-title":"IFIP","first-page":"241","volume-title":"IFIP TCS 2008","author":"R. Saikkonen","year":"2008","unstructured":"Saikkonen, R., Soisalon-Soininen, E.: Cache-sensitive memory layout for binary trees. In: Ausiello, G., Karhum\u00e4ki, J., Mauri, G., Ong, L. (eds.) IFIP TCS 2008. IFIP, vol.\u00a0273, pp. 241\u2013255. Springer, Boston (2008)"},{"issue":"6","key":"13_CR19","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","volume":"7","author":"J.W.J. Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: Heapsort. Commun. ACM\u00a07(6), 347\u2013348 (1964)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38527-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T13:19:43Z","timestamp":1645017583000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38527-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385261","9783642385278"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38527-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}