{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T17:02:10Z","timestamp":1759683730361},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>Searching in sorted arrays of keys is a common task with a broad range of applications. Often searching is part of the performance critical sections of a database query or index access, raising the question what kind of search algorithm to choose and how to optimize it to obtain the best possible performance on real-world hardware. This paper strives to answer this question by evaluating a large set of optimized sequential, binary and k-ary search algorithms on a modern processor. In this context, we consider hardware-sensitive optimization strategies as well as algorithmic variations resulting in an eight-dimensional evaluation space.<\/jats:p>\n          <jats:p>As a result, we give insights on expected interactions between search algorithms and optimizations on modern hardware. In fact, there is no single best optimized algorithm, leading to a set of advices on which variants should be considered first given a particular array size.<\/jats:p>","DOI":"10.14778\/3236187.3236205","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1550-1562","source":"Crossref","is-referenced-by-count":10,"title":["An eight-dimensional systematic evaluation of optimized search algorithms on modern processors"],"prefix":"10.14778","volume":"11","author":[{"given":"Lars-Christian","family":"Schulz","sequence":"first","affiliation":[{"name":"University of Magdeburg, Magdeburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Broneske","sequence":"additional","affiliation":[{"name":"University of Magdeburg, Magdeburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunter","family":"Saake","sequence":"additional","affiliation":[{"name":"University of Magdeburg, Magdeburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Intel 64 and IA-32 Architectures Optimization Reference Manual Nov. 2016.  Intel 64 and IA-32 Architectures Optimization Reference Manual Nov. 2016."},{"key":"e_1_2_1_2_1","unstructured":"Intel 64 and IA-32 Architectures Software Developer's Manual Dec. 2016.  Intel 64 and IA-32 Architectures Software Developer's Manual Dec. 2016."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.118"},{"key":"e_1_2_1_4_1","volume-title":"Exploiting capabilities of modern processors in data intensive applications. it -Information Technology, 59(3):133--140","author":"Broneske D.","year":"2017"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656370"},{"key":"e_1_2_1_6_1","volume-title":"Computer Architecture: A Quantitative Approach. Morgan Kaufmann","author":"Hennessy J. L.","year":"2011"},{"key":"e_1_2_1_7_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth D.","year":"1998"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196909"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544812"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/26.2.154"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335449"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1565694.1565705"},{"key":"e_1_2_1_13_1","volume-title":"Searching in sorted lists on modern processors. Bachelor's thesis","author":"Schulz L.-C.","year":"2017"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT). OpenProceedings.org","author":"Zeuch S.","year":"2014"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564709"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:40:52Z","timestamp":1672220452000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":15,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236205"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236205","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}