caa a22 4500 44580551X CHVBK 20180317145155.0 cr unu---uuuuu 170323e20111001xx s 000 0 eng 10.1007/s00453-010-9394-0 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9394-0 The Cost of Cache-Oblivious Searching [Elektronische Daten] [Michael Bender, Gerth Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, Alejandro López-Ortiz] This paper gives tight bounds on the cost of cache-oblivious searching. The paper shows that no cache-oblivious search structure can guarantee a search performance of fewer than lg elog B N memory transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. The paper gives modified versions of the van Emde Boas layout, where the expected number of memory transfers between any two levels of the memory hierarchy is arbitrarily close to [lg e+O(lg lg B/lg B)]log B N+O(1). This factor approaches lg e≈1.443 as B increases. The expectation is taken over the random placement in memory of the first element of the structure. Because searching in the disk-access machine (DAM) model can be performed in log B N+O(1) block transfers, this result establishes a separation between the (2-level) DAM model and cache-oblivious model. The DAM model naturally extends to k levels. The paper also shows that as k grows, the search costs of the optimal k-level DAM search structure and the optimal cache-oblivious search structure rapidly converge. This result demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure. Springer Science+Business Media, LLC, 2010 Cache-oblivious B-tree nationallicence Cache-oblivious searching nationallicence van Emde Boas layout nationallicence Bender Michael Department of Computer Science, Stony Brook University, 11794-4400, Stony Brook, NY, USA aut Brodal Gerth MADALGO—Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Department of Computer Science, Aarhus University, Ny Munkegade, 8000, Århus C, Denmark aut Fagerberg Rolf Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230, Odense M, Denmark aut Ge Dongdong Department of Management Science and Engineering, Antai School of Economics and Management, Shanghai JiaoTong University, 200052, Shanghai, China aut He Simai Department of System Engineering and Engineering Management, Chinese University of Hongkong, Hongkong, China aut Hu Haodong Networking and Device Connectivity at Windows Division, Microsoft, 98052, Redmond, WA, USA aut Iacono John Department of Computer and Information Science, Polytechnic University, 11201, Brooklyn, NY, USA aut López-Ortiz Alejandro School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontarion, Canada aut Algorithmica Springer-Verlag 61/2(2011-10-01), 463-505 0178-4617 61:2<463 2011 61 453 https://doi.org/10.1007/s00453-010-9394-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9394-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bender Michael Department of Computer Science, Stony Brook University, 11794-4400, Stony Brook, NY, USA aut NATIONALLICENCE 700 1- Brodal Gerth MADALGO—Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, Department of Computer Science, Aarhus University, Ny Munkegade, 8000, Århus C, Denmark aut NATIONALLICENCE 700 1- Fagerberg Rolf Department of Mathematics and Computer Science, University of Southern Denmark, Campusvej 55, 5230, Odense M, Denmark aut NATIONALLICENCE 700 1- Ge Dongdong Department of Management Science and Engineering, Antai School of Economics and Management, Shanghai JiaoTong University, 200052, Shanghai, China aut NATIONALLICENCE 700 1- He Simai Department of System Engineering and Engineering Management, Chinese University of Hongkong, Hongkong, China aut NATIONALLICENCE 700 1- Hu Haodong Networking and Device Connectivity at Windows Division, Microsoft, 98052, Redmond, WA, USA aut NATIONALLICENCE 700 1- Iacono John Department of Computer and Information Science, Polytechnic University, 11201, Brooklyn, NY, USA aut NATIONALLICENCE 700 1- López-Ortiz Alejandro School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontarion, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/2(2011-10-01), 463-505 0178-4617 61:2<463 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer