Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Bast, Holger Dietzfelbinger, Martin Hagerup, Torben dblp dblp dblp Not MPG Author(s): Dietzfelbinger, Martin
 Editor(s):
 BibTeX cite key*: BastDH92

 Title, Booktitle
 Title*: A Perfect Parallel Dictionary Booktitle*: 17th International Symposium on Mathematical Foundations of Computer Science (MFCS'92)

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: Prague, Czechoslovakia Language: English Event Date* (no longer used): Organization: Event Start Date: 24 August 2002 Event End Date: 28 August 2002

 Publisher
 Name*: Springer URL: Address*: New York, NY, USA Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 629 Number: Month: Pages: 133-141 Year*: 1992 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (LaTeX) 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 \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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{BastDH92,
AUTHOR = {Bast, Holger and Dietzfelbinger, Martin and Hagerup, Torben},
TITLE = {A Perfect Parallel Dictionary},
BOOKTITLE = {17th International Symposium on Mathematical Foundations of Computer Science (MFCS'92)},
PUBLISHER = {Springer},
YEAR = {1992},
VOLUME = {629},
PAGES = {133--141},
SERIES = {Lecture Notes in Computer Science},