Abstract

Exponential Tree in the form of forest is proposed in such a manner that- (a) it provides faster access of a node and, (b) it becomes more compatible with the parallel environment. Empirically, it has been show that the proposed method decreases the total internal path length of an Exponential Tree quite considerably. The experiments were conducted by creating three different data structures using the same input- a conventional binary tree, a forest of hashed binary trees and a forest of hashed exponential trees. It has been shown that a forest of hashed exponential trees so produced has lesser internal path length and height in comparison of other two. It also increases the degree of parallelism.

References

• A. Anderson "Fast deterministic sorting and searching in linear space", IEEE Symposium on Foundations of Computer Science, 1996.
• R. Raman "Priority queues: small, monotone and trans-dichotomous" in European Symposium on Algorithms, 1996.
• Y. Han. 2002 "Deterministic sorting in O (n log logn) time and linear space" in 34th STOC.
• Ajit Singh, Dr. Deepak Garg "Implementation and Performance Analysis of Exponential Tree Sorting ", International Journal of Computer Applications, 2011.
• Samadhi "B Trees in System with Multiple Users" in Information Processing Letters, 107-112, 1976.
• Eswaran, K. P. , Gray, J. N Lorie, R. A. and Traiger, I. L "The notions of Consistency and Predicate Locks in a Database System" in Communication of the ACM, 1976.
• Bayer, R, Schkolnick "Concurrency of Operations on B Trees" in Acta Information, 1977.
• Ries, D. R. , Stonebreaker "Effects of Locking Granularity in a Database Management System" in ACM Transaction on Database Systems, 1977.
• Ellis, C. S. "Concurrency search and insertion in AVL trees" in IEEE Transactions on Computers, 1980.
• Ellis, C. S. "Concurrency search and insertion in 2-3 trees". Acta Information, 1980.
• Kung, H. T. , Lehman, P. L. "Concurrent manipulation of binary search trees" in ACM Transaction on Database Systems, 1980.
• Knuth, D. E. "The Art of Computer Programming" in Pearson Education, Vol. 3, Searching and Sorting, 2005.
• Y. Han, M. Thorup. "Sorting integers in O (n?loglogn) expected time and linear space" in IEEE Symposium on Foundations of Computer Science, Vol-43, 2002.
• Day, A. C. "Balancing a Binary Tree" in Computer Journal, 1976.
• Stout, F, Bette, L. W. "Tree Rebalancing in Optimal Time and Space in Communication of the ACM", 1986.
• S. Alberts, T. Hagerup. "Improved parallel integer sorting without concurrent writing in Information and Computation, 1997.