Published Articles >> Table of Contents >> Abstract

44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)   p. 271
The Cost of Cache-Oblivious Searching
Michael A. Bender, State University of New York at Stony Brook and Sandia National Laboratories
Gerth Stolting Brodal, University of Aarhus and Carlsberg Foundation
Rolf Fagerberg, University of Aarhus
Dongdong Ge, State University of New York at Stony Brook
Simai He, State University of New York at Stony Brook
Haodong Hu, State University of New York at Stony Brook
John Iacono, Polytechnic University, Brooklyn
Alejandro Lopez-Ortiz, University of Waterloo

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2003.1238201
Send link to a friend

Abstract
Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e logB N block 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. A modified version of the van Emde Boas layout is proposed, whose expected block transfers between any two levels of the memory hierarchy arbitrarily close to [lg e + O(lg lg B/ lgB)] logB N + O(1). This factor approaches lg e \approx 1.443 as B increases. The expectation is taken over the random placement of the first element of the structure in memory. As searching in the Disk Access Model (DAM) can be performed in logB N + 1 block transfers, this result shows a separation between the 2-level DAM and cache-oblivious memory-hierarchy models. By extending the DAM model to k levels, multilevel memory hierarchies can be modelled. It is shown that as k grows, the search costs of the optimal k-level DAM search structure and of the optimal cache-oblivious search structure rapidly converge. This demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure.
Back to Top Additional Information
Citation:  Michael A. Bender, Gerth Stolting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, Alejandro Lopez-Ortiz, "The Cost of Cache-Oblivious Searching," focs, p. 271,  44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03),  2003