A locality-preserving cache-oblivious dynamic dictionary

ABSTRACT

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. Like the cache-oblivious B-tree, this structure supports search operations using only O(logBN) block operations at a level of the memory hierarchy with block size B. Insertion and deletion operations use O(logBN + log² N/B) amortized block transfers. Finally, the data structure returns all k data items in a given search range using O(logBN + k/B) block operations.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.

REFERENCES

• 1: G. M. Adel'son-Vel'skiǐ and E. M. Landis. An algorithm for organization of information (in Russian). Doklady Akademii Nauk SSSR, 146:263-266, 1962.
• 2: A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
• 3: Alok Aggarwal , Ashok Chandra, Virtual memory algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.173-185, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62227]
• 4: A. Aggarwal, A. K. Chandra, and M. Snir. Hierarchical memory with block transfer. In Proc. IEEE Symp. on Foundations of Computer Science, pages 204-216, 1987.
• 5: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 6: B. Alpern, L. Carter, E. Feig, and T. Selker. The uniform memory hierarchy model of computation. Algorithmica, 12(2-3):72-109, 1994.
• 7: A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
• 8: Arne A. Andersson , Mikkel Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.335-342, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335344]
• 9: Lars Arge , Klaus Hinrichs , Jan Vahrenhold , Jeffrey Scott Vitter, Efficient Bulk Operations on Dynamic R-trees, Selected papers from the International Workshop on Algorithm Engineering and Experimentation, p.328-348, January 15-16, 1999
• 10: R. Bayer and E. M. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1(3):173-189, 1972.
• 11: M. A. Bender , E. D. Demaine , M. Farach-Colton, Cache-oblivious B-trees, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.399, November 12-14, 2000
• 12: Gianfranco Bilardi , Paolo D'Alberto , Alexandru Nicolau, Fractal Matrix Multiplication: A Case Study on Portability of Cache Performance, Proceedings of the 5th International Workshop on Algorithm Engineering, p.26-38, August 28-31, 2001
• 13: Robert D. Blumofe , Matteo Frigo , Christopher F. Joerg , Charles E. Leiserson , Keith H. Randall, An analysis of dag-consistent distributed shared-memory algorithms, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.297-308, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237574]
• 14: Gerth Stølting Brodal , Rolf Fagerberg , Riko Jacob, Cache oblivious search trees via binary trees of small height, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.39-48, January 06-08, 2002, San Francisco, California
• 15: M. R. Brown and R. E. Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM J. Comput., 9:594-614, 1980.
• 16: D. Carlson. Software design using c++. http://cis.stvincent.edu/carlsond/swdesign/swd.html, 2001.
• 17: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 18: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 19: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 20: Jim Gray , Goetz Graefe, The five-minute rule ten years later, and other computer storage rules of thumb, ACM SIGMOD Record, v.26 n.4, p.63-68, Dec. 1997 [doi>10.1145/271074.271094]
• 21: L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. In Proc. Symp. on Foundations of Computer Science, pages 8-21, 1978.
• 22: S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157-184, 1982.
• 23: John Iacono, Alternatives to splay trees with O(log n) worst-case access times, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.516-522, January 07-09, 2001, Washington, D.C., United States
• 24: Alon Itai , Alan G. Konheim , Michael Rodeh, A Sparse Table Implementation of Priority Queues, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.417-431, July 13-17, 1981
• 25: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 26: Kihong Kim , Sang K. Cha, Sibling clustering of tree-based spatial indexes for efficient spatial query processing, Proceedings of the seventh international conference on Information and knowledge management, p.398-405, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288686]
• 27: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 28: Robert L. Kruse , Alexander J. Ryba, Data structures and program design in C++, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 29: R. Meville and D. Gries. Controlled density sorting. Infor. Process. Lett., 10:169-172, 1980.
• 30: J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing, 2:33-43, 1973.
• 31: H. Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 1999.
• 32: H. Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 1999.
• 33: William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Proceedings of the Workshop on Algorithms and Data Structures, p.437-449, August 17-19, 1989
• 34: Naila Rahman , Richard Cole , Rajeev Raman, Optimised Predecessor Data Structures for Internal Memory, Proceedings of the 5th International Workshop on Algorithm Engineering, p.67-78, August 28-31, 2001
• 35: Vijayshankar Raman, Locality preserving dictionaries: theory & application to clustering in databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.337-345, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304009]
• 36: John E. Savage, Extending the Hong-Kung Model to Memory Hierarchies, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.270-281, August 24-26, 1995
• 37: R. Seidel and C. R. Aragon. Randomized search trees. Algorithmica, 16(4-5):464-497, 1996.
• 38: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 39: Mikkel Thorup, Faster deterministic sorting and priority queues in linear space, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.550-555, January 25-27, 1998, San Francisco, California, United States
• 40: Sivan Toledo, Locality of Reference in LU Decomposition with Partial Pivoting, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.1065-1081, Oct. 1997 [doi>10.1137/S0895479896297744]
• 41: P. van Emde Boas. Preserving order in a forest in less than logarithmic time. In Proc. Symp. on Foundations of Computer Science, pages 75-84, 1975.
• 42: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10(2):99-127, 1977.
• 43: Jeffrey Scott Vitter, External memory algorithms and data structures, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 44: J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory II: Hierarchical multilevel memories. Algorithmica, 12(2-3):148-169, 1994.
• 45: D. E. Willard. Inserting and deleting records in blocked sequential files. Technical Report TM81-45193-5, Bell Laboratories, 1981.
• 46: Dan E. Willard, Maintaining dense sequential files in a dynamic environment (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.114-121, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802183]
• 47: Dan E. Willard, Good worst-case algorithms for inserting and deleting records in dense sequential files, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.251-260, May 28-30, 1986, Washington, D.C., United States
• 48: Dan E. Willard, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Information and Computation, v.97 n.2, p.150-204, April 1992 [doi>10.1016/0890-5401(92)90034-D]
• 49: Qing Yi , Vikram Adve , Ken Kennedy, Transforming loops to recursion for multi-level memory hierarchies, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.169-181, June 18-21, 2000, Vancouver, British Columbia, Canada