TY - GEN

T1 - On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications

AU - Siegel, Alan

PY - 1989

Y1 - 1989

N2 - A mechanism is provided for constructing log-n--wise-independent hash functions that can be evaluated in O(1) time. A probabilistic argument shows that for fixed ε < 1, a table of nε random words can be accessed by a small O(1)-time program to compute one important family of hash functions. An explicit algorithm for such a family, which achieves comparable performance for all practical purposes, is also given. A lower bound shows that such a program must take Ω(k/ε) time, and a probabilistic argument shows that programs can run in O(k2/ε2) time. An immediate consequence of these constructions is that double hashing using these universal functions has (constant factor) optimal performance in time, for suitably moderate loads. Another consequence is that a T-time PRAM (parallel random-access machine) algorithm for n log n processors (and nk memory) can be emulated on an n-processor machine interconnected by an n × log n Omega network with a multiplicative penalty for total work that, with high probability, is only O(1).

AB - A mechanism is provided for constructing log-n--wise-independent hash functions that can be evaluated in O(1) time. A probabilistic argument shows that for fixed ε < 1, a table of nε random words can be accessed by a small O(1)-time program to compute one important family of hash functions. An explicit algorithm for such a family, which achieves comparable performance for all practical purposes, is also given. A lower bound shows that such a program must take Ω(k/ε) time, and a probabilistic argument shows that programs can run in O(k2/ε2) time. An immediate consequence of these constructions is that double hashing using these universal functions has (constant factor) optimal performance in time, for suitably moderate loads. Another consequence is that a T-time PRAM (parallel random-access machine) algorithm for n log n processors (and nk memory) can be emulated on an n-processor machine interconnected by an n × log n Omega network with a multiplicative penalty for total work that, with high probability, is only O(1).

UR - http://www.scopus.com/inward/record.url?scp=0024768554&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024768554&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1989.63450

DO - 10.1109/sfcs.1989.63450

M3 - Conference contribution

AN - SCOPUS:0024768554

SN - 0818619821

SN - 9780818619823

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 20

EP - 25

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

T2 - 30th Annual Symposium on Foundations of Computer Science

Y2 - 30 October 1989 through 1 November 1989

ER -