ylfink@water.waterloo.edu (ylfink) (06/04/88)
DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES
DATA STRUCTURING SEMINAR
- Tuesday, June 7, 1988
Dr. Jeanette P. Schmidt, Courant Institute, New York
University, will speak on ``Non-Oblivious Hashing''.
TIME: 3:30 PM
ROOM: DC 1302
ABSTRACT
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 O(1) worst case scheme that requires only
-
logarithmic additional memory (improving on the
linear space upper bound).
b) An almost sure O(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 O(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.
June 3, 1988