Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Fast and Reliable Parallel Hashing

MPG-Autoren
/persons/resource/persons44076

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

/persons/resource/persons44564

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte in PuRe verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Bast, H., & Hagerup, T. (1991). Fast and Reliable Parallel Hashing. In 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA'91) (pp. 50-61). New York, NY, USA: ACM.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-AE37-8
Zusammenfassung
A perfect hash function for a (multi)set $X$ of
$n$ integers is an injective function $h:X\to\{1,\ldots,s\}$,
where $s=O(n)$, that can be stored in $O(n)$ space
and evaluated in constant time by a single processor.
We show that a perfect hash function for a given
multiset of $n$ integers can be constructed
optimally in $O(\log^* n)$ time using
$O(n/\log^* n)$ processors.
Our algorithm is faster than all previously published
methods.
More significantly, it is highly
reliable:
Whereas analyses of previous fast parallel
hashing schemes provided bounds on the expected
resource requirements only, our algorithm is
guaranteed to stay within the bounds given
with overwhelming probability.