Clark D. Thompson and Michael J. Carey

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-82-101
April 1982

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/CSD-82-101.pdf

A scheme for maintaining a balanced search tree on O(lg N) parallel processors is described. O(lg N) search, insert, and delete operations are allowed to run concurrently, with each operation executing in O(lg N) timesteps. The scheme is based on pipelined versions of top-down 2-3-4 tree manipulation algorithms.

BibTeX citation:

@techreport{Thompson:CSD-82-101,
    Author = {Thompson, Clark D. and Carey, Michael J.},
    Title = {An Efficient Implementation of Search Trees on O(lg N) Processors},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1982},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6204.html},
    Number = {UCB/CSD-82-101},
    Abstract = {A scheme for maintaining a balanced search tree on O(lg N) parallel processors is described. O(lg N) search, insert, and delete operations are allowed to run concurrently, with each operation executing in O(lg N) timesteps. The scheme is based on pipelined versions of top-down 2-3-4 tree manipulation algorithms.}
}

EndNote citation:

%0 Report
%A Thompson, Clark D.
%A Carey, Michael J.
%T An Efficient Implementation of Search Trees on O(lg N) Processors
%I EECS Department, University of California, Berkeley
%D 1982
%@ UCB/CSD-82-101
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1982/6204.html
%F Thompson:CSD-82-101