- Authors:
- Clark D. Thompson,
- Michael J. Carey
A scheme for maintaining a balanced search tree on O(lgN) parallel processors is described. O(lgN) search, insert, and delete operations are allowed to run concurrently, with each operation executing in O(lgN) timesteps. The scheme is based on pipelined versions of top-down 2-3-4 tree manipulation algorithms.
Cited By
- Wah B and Li G (1986). Survey on special purpose computer architectures for AI, ACM SIGART Bulletin:96, (28-46), Online publication date: 1-Apr-1986.
- Fisher A (2019). Dictionary machines with a small number of processors, ACM SIGARCH Computer Architecture News, 12:3, (151-156), Online publication date: 1-Jun-1984.
- Fisher A Dictionary machines with a small number of processors Proceedings of the 11th annual international symposium on Computer architecture, (151-156)
- Carey M and Thompson C (1984). An Efficient Implementation of Search Trees on [lg N + 1] Processors, IEEE Transactions on Computers, 33:11, (1038-1041), Online publication date: 1-Nov-1984.
Recommendations
An Efficient Implementation of Search Trees on [lg N + 1] Processors
A scheme for maintaining a balanced search tree on ?lg N + 1?parallel processors is described. The scheme is almost fully pipelined: ?lg N + 1?/2 search, insert, and delete operations may run concurrently. Each processor executes 0(1) instructions of a ...
O(log log n)-competitive dynamic binary search trees
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithmThe Dynamic Optimality Conjecture [ST85] states that splay trees are competitive (within a constant competitive factor) among the class of all binary search tree (BST) algorithms. Despite 20 years of research this conjecture is still unresolved. ...