A Perfect Parallel Dictionary

Abstract We describe new randomized parallel algorithms for the problems of interval allocation, construction of static dictionaries, and maintenance of dynamic dictionaries. All of our algorithms run optimally in constant time with high probability. Our main result is the construction of what we call a perfect dictionary, a scheme that allows p processors implementing a set M in space proportional to ¦M¦ to process batches of p insert, delete, and lookup instructions on M in constant time pet batch. Our best results are obtained for a new variant of the CRCW PRAM model of computation called the OR PRAM. For other variants of the CRCW PRAM we show slightly weaker results, with some resource bounds increased by a factor of ⊖(log k n ), where k ∈ ℕ is fixed but arbitrarily large.

Authors

• Hannah Bast
• Martin Dietzfelbinger
• Torben Hagerup

Keywords

No keywords are indexed for this paper.