Loading...
Loading...

Go to the content (press return)

A Top-down design of a parallel dictionary using skip lists

Author
Gabarro, J.; Martinez, C.; Messeguer, X.
Type of activity
Report
Date
1994-02
Code
LSI-94-11-R
Repository
http://hdl.handle.net/2117/96672 Open in new window
Abstract
We present a top down design of a parallel PRAM dictionary using skip lists. More precisely, we give algorithms to search, insert or delete k elements in a skip list of n elements, in parallel. The algorithms are simple and easy to implement on real machines. All of them are iterative. They can be implemented in the EREW PRAM model using k processors in expected time O(log n + log k). The probability that there is a significant deviation from the expected time decreases as O(n^{-2}) for the sear...
Citation
Gabarro, J., Martinez, C., Messeguer, X. "A Top-down design of a parallel dictionary using skip lists". 1994.
Keywords
EREW PRAM, PRAM
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods
CEBIM - Molecular Biotechnology Centre

Participants

Attachments