TY - JOUR
T1 - The cost of cache-oblivious searching
AU - Bender, Michael A.
AU - Brodal, Gerth Stølting
AU - Fagerberg, Rolf
AU - Ge, Dongdong
AU - He, Simai
AU - Hu, Haodong
AU - Iacono, John
AU - López-Ortiz, Alejandro
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2011/10
Y1 - 2011/10
N2 - 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.
AB - 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.
KW - Cache-oblivious B-tree
KW - Cache-oblivious searching
KW - van Emde Boas layout
UR - http://www.scopus.com/inward/record.url?scp=80051545082&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051545082&partnerID=8YFLogxK
U2 - 10.1007/s00453-010-9394-0
DO - 10.1007/s00453-010-9394-0
M3 - Article
AN - SCOPUS:80051545082
SN - 0178-4617
VL - 61
SP - 463
EP - 505
JO - Algorithmica (New York)
JF - Algorithmica (New York)
IS - 2
ER -