English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  A Perfect Parallel Dictionary

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AE08-3 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-AE09-1
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Bast, Holger1, Author           
Dietzfelbinger, Martin1, Author           
Hagerup, Torben1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2006-06-091992
 Publication Status: Issued
 Pages: -
 Publishing info: New York, NY, USA : Springer
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518234
Other: Local-ID: C1256428004B93B8-4E4D7FF9DA53FF69C1257188004855D7-BastDH92
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Prague, Czechoslovakia
Start-/End Date: 1992-08-24 - 1992-08-28

Legal Case

show

Project information

show

Source 1

show
hide
Title: 17th International Symposium on Mathematical Foundations of Computer Science (MFCS'92)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, NY, USA : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 133 - 141 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -