Key points are not available for this paper at this time.
Optmaahty questions are examined m the following information retrieval problem. Given a set S of n keys, store them so that queries of the form, "Is x E S?" can be answered quickly It is shown that m a rather general model including all the commonly used schemes, lg(n + I) probes to the table are needed m the worst case, prowded the key space is sufficiently large The effects of smaller key space and arbitrary encoding are also explored
Andrew Chi-Chih Yao (Wed,) studied this question.