Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Gabarro, J.; Martinez, C.; Messeguer, X.
Tipus d'activitat
Document cientificotècnic
Data
1994-02
Codi
LSI-94-11-R
Repositori
http://hdl.handle.net/2117/96672 Obrir en finestra nova
Resum
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...
Citació
Gabarro, J., Martinez, C., Messeguer, X. "A Top-down design of a parallel dictionary using skip lists". 1994.
Paraules clau
EREW PRAM, PRAM
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
CEBIM - Centre de Biotecnologia Molecular

Arxius