Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A Perfect Parallel Dictionary

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

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AE08-3 Versions-Permalink: https://hdl.handle.net/21.11116/0000-000E-4CE3-D
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
https://rdcu.be/dwYw5 (Verlagsversion)
Beschreibung:
-
OA-Status:
Keine Angabe

Urheber

einblenden:
ausblenden:
 Urheber:
Bast, Holger1, Autor           
Dietzfelbinger, Martin1, Autor           
Hagerup, Torben1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-06-091992
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518234
Anderer: Local-ID: C1256428004B93B8-4E4D7FF9DA53FF69C1257188004855D7-BastDH92
DOI: 10.1007/3-540-55808-X_11
BibTex Citekey: Bast-et-al_MFCS92
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 17th International Symposium on Mathematical Foundations of Computer Science
Veranstaltungsort: Prague, Czechoslovakia
Start-/Enddatum: 1992-08-24 - 1992-08-28

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Mathematical Foundations of Computer Science 1992
  Untertitel : 17th International Symposium
  Kurztitel : MFCS 1992
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: New York, NY, USA : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 133 - 141 Identifikator: ISBN: 978-3-540-55808-8

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 629 Artikelnummer: - Start- / Endseite: - Identifikator: -