de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

A Perfect Parallel Dictionary

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44076

Bast,  Holger
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44318

Dietzfelbinger,  Martin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44564

Hagerup,  Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Bast, H., Dietzfelbinger, M., & Hagerup, T. (1992). A Perfect Parallel Dictionary. In 17th International Symposium on Mathematical Foundations of Computer Science (MFCS'92) (pp. 133-141). New York, NY, USA: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-AE08-3
Zusammenfassung
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 \emph{perfect dictionary}, a scheme that allows $p$ processors implementing a set $M$ in space proportional to $|M|$ to process batches of $p$ \emph{insert}, \emph{delete}, and \emph{lookup} instructions on $M$ in constant time per 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 $\Theta(\log^k n)$, where $k\in\IN$ is fixed but arbitrarily large.