TY - GEN

T1 - Non-oblivious hashing

AU - Fiat, Amos

AU - Naor, Moni

AU - Schmidt, Jeanette P.

AU - Siegel, Alan

PY - 1988

Y1 - 1988

N2 - Non-oblivious hashing, where the information gathered by performing "unsuccessful" probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.

AB - Non-oblivious hashing, where the information gathered by performing "unsuccessful" probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.

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

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

U2 - 10.1145/62212.62248

DO - 10.1145/62212.62248

M3 - Conference contribution

AN - SCOPUS:0346195541

SN - 0897912640

SN - 9780897912648

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 367

EP - 376

BT - Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988

PB - Association for Computing Machinery

T2 - 20th Annual ACM Symposium on Theory of Computing, STOC 1988

Y2 - 2 May 1988 through 4 May 1988

ER -