ReducedCBT and SuperCBT: two new and improved complete binary tree structures

Between the leaves and the nodes of a complete binary tree, a separate parent-child-sister hierarchy is employed independent of the parent-child-sister hierarchy used for the rest of the tree. Two different versions of such a local hierarchy are introduced. The result of the first proposed hierarchy is a faster and smaller footprint, while the second one provides size variation functionality without a significant computational overhead. Complexity comparison between the algorithms based on the introduced local hierarchies and ones based on previous complete binary tree structures reveals that the novel approach brings considerable memory gains and performance boosts to the complete binary tree based algorithms.

PDF

___

[1] Brodal GS, Fagerberg R, Vinther K. Engineering a cache-oblivious sorting algorithm. ACM J Exp Algorithmics 2007; 12: 2.2.
[2] Kim C, Chhugani J, Satish N, Sedlar E, Nguyen AD, Kaldewey T, Lee VW, Brandt SA, Dubey P. FAST: Fast architecture sensitive tree search on modern CPUs and GPUs. In: 2010 ACM SIGMOD/PODS Conference; 2010; Indianapolis, IN, USA.
[3] Mar´ın M. On the pending event set and binary tournaments. In: 10th SCS European Simulation Symposium, Society for Computer Simulation Europe Publishing House; 1998. pp. 110-114.
[4] Mar´ın M, Risso D, Cordero P. Efficient algorithms for many-body hard particle molecular dynamics. J Comput Phys 1993; 109: 306-317.
[5] Knuth DE. The Art of Computer Programming. 2nd ed. New York, NY, USA: Addison-Wesley, 1998.
[6] Mar´ın M, Risso D, Cordero P. An empirical assessment of priority queues in event-driven molecular dynamics simulation. Comput Phys Commun 1995; 92: 214-224.
[7] Bulut M, Camata R. A generalized cell method for hard disk molecular dynamics simulation of polydisperse systems. Int J Mod Phys C 2007; 9: 1407-1416.
[8] Lubachevsky BD. How to simulate billiards and similar systems. J Comput Phys 1991; 94: 255-283.
[9] Allen M. Introduction to molecular dynamics simulation. In: Attig N, Binder K, Grubmuller H, Kremer K, editors. Computational Soft Matter: From Synthetic Polymers to Proteins. J¨ulich, Germany: John von Neumann Institute for Computing, 2004. pp. 1-28.
[10] Brown R. Calendar queues: a fast O(1) priority queue implementation for the simulation event set problem. Commun ACM 1988; 10: 1220-1227.
[11] Paul G. A complexity O(1) priority queue for event driven molecular dynamics simulations. J Comput Phys 2007; 221: 615-625.
[12] Mar´ın M. An Empirical Comparison of Priority Queue Algorithms. Oxford, UK: University of Oxford, 1997.
[13] Graham RL, Knuth DE, Patashnik O. Concrete Mathematics. 2nd ed. New York, NY, USA: Addison-Wesley, 2006.
[14] Bulut M. Experimental and Theoretical Studies on Aerosol Nanoparticles, VDM, Saarbr¨ucken, Germany, 2008.