Cache oblivious search trees via binary trees of small height

ABSTRACT

We propose a version of cache oblivious search trees which is simpler than the previous proposal of Bender, Demaine and Farach-Colton and has the same complexity bounds. In particular, our data structure avoids the use of weight balanced B-trees, and can be implemented as just a single array of data elements, without the use of pointers. The structure also improves space utilization.For storing n elements, our proposal uses (1 + ε)n times the element size of memory, and performs searches in worst case O(logB n) memory transfers, updates in amortized O((log² n)/(εB)) memory transfers, and range queries in worst case O(logB n + k/B) memory transfers, where k is the size of the output.The basic idea of our data structure is to maintain a dynamic binary tree of height log n+O(1) using existing methods, embed this tree in a static binary tree, which in turn is embedded in an array in a cache oblivious fashion, using the van Emde Boas layout of Prokop.We also investigate the practicality of cache obliviousness in the area of search trees, by providing an empirical comparison of different methods for laying out a search tree in memory.

REFERENCES

• 1: 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]
• 2: A. Andersson , T. W. Lai, Fast updating of well-balanced trees, Proceedings of the second Scandinavian workshop on Algorithm theory, p.111-121, July 1990, Bergen, Sweden
• 3: L. Arge , J. S. Vitter, Optimal dynamic interval management in external memory, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.560, October 14-16, 1996
• 4: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173-189, 1972.
• 5: 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
• 6: Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.29-38, January 06-08, 2002, San Francisco, California
• 7: Svante Carlsson , J. Ian Munro , Patricio V. Poblete, An implicit binomial queue with constant insertion time, No. 318 on SWAT 88: 1st Scandinavian workshop on algorithm theory, p.1-13, January 1988, Halmstad, Sweden
• 8: Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305231]
• 9: P. F. Dietz , J. Zhang, Lower bounds for monotonic list labeling, Proceedings of the second Scandinavian workshop on Algorithm theory, p.173-180, July 1990, Bergen, Sweden
• 10: Rolf Fagerberg, The Complexity of Rebalancing a Binary Serach Tree, Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, p.72-83, December 13-15, 1999
• 11: A. Fiat, J. I. Munro, M. Naor, A. A. Schäffer, J. P. Schmidt, and A. Siegel. An implicit data structure for searching a multikey table in logarithmic time. Journal of Computer and System Sciences, 43(3):406-424, 1991.
• 12: 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
• 13: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 14: 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
• 15: Douglas W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM, v.29 n.4, p.300-311, April 1986 [doi>10.1145/5684.5686]
• 16: Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996 [doi>10.1145/235141.235145]
• 17: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 18: J Ian Munro, An implicit data structure supporting insertion, deletion, and search in O(log:OS2:OEn) time, Journal of Computer and System Sciences, v.33 n.1, p.66-74, Aug. 1986 [doi>10.1016/0022-0000(86)90043-7]
• 19: H. Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology, June 1999.
• 20: 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
• 21: P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett., 6:80-82, 1977.
• 22: P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, 1977.
• 23: J. W. J. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347-348, 1964.