TY - JOUR
T1 - A locality-preserving cache-oblivious dynamic dictionary
AU - Bender, Michael A.
AU - Duan, Ziyang
AU - Iacono, John
AU - Wu, Jing
N1 - Funding Information:
✩ This work appeared in preliminary form in the Proceedings of the 13th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pp. 29–38, January 2002. * Corresponding author. E-mail addresses: [email protected] (M.A. Bender), [email protected] (Z. Duan), [email protected] (J. Iacono), [email protected] (J. Wu). 1 Supported in part by NSF Grants ACI-032497, CCR-0208670, and EIA-0112849, HRL Laboratories, and Sandia National Laboratories.
PY - 2004/11
Y1 - 2004/11
N2 - This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache-oblivious and locality-preserving. A cache-oblivious data structure has memory performance optimized for all levels of the memory hierarchy even though it has no memory-hierarchy-specific parameterization. A locality-preserving dictionary maintains elements of similar key values stored close together for fast access to ranges of data with consecutive keys. The data structure presented here is a simplification of the cache-oblivious B-tree of Bender, Demaine, and Farach-Colton. The structure supports search operations on N data items using O(logBN + 1) block transfers at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(logBN + log2N/B + 1) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(logBN + k/B + 1) block transfers. This data structure was implemented and its performance was evaluated on a simulated memory hierarchy. This paper presents the results of this simulation for various combinations of block and memory sizes.
AB - This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache-oblivious and locality-preserving. A cache-oblivious data structure has memory performance optimized for all levels of the memory hierarchy even though it has no memory-hierarchy-specific parameterization. A locality-preserving dictionary maintains elements of similar key values stored close together for fast access to ranges of data with consecutive keys. The data structure presented here is a simplification of the cache-oblivious B-tree of Bender, Demaine, and Farach-Colton. The structure supports search operations on N data items using O(logBN + 1) block transfers at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(logBN + log2N/B + 1) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(logBN + k/B + 1) block transfers. This data structure was implemented and its performance was evaluated on a simulated memory hierarchy. This paper presents the results of this simulation for various combinations of block and memory sizes.
UR - http://www.scopus.com/inward/record.url?scp=3943062182&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=3943062182&partnerID=8YFLogxK
U2 - 10.1016/j.jalgor.2004.04.014
DO - 10.1016/j.jalgor.2004.04.014
M3 - Article
AN - SCOPUS:3943062182
SN - 0196-6774
VL - 53
SP - 115
EP - 136
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 2
ER -