Performance measurement and data base design
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
A.C. Yao (1981) has determined the maximal size of a finite universe U such that it is possible to store all subsets A of U with k elements in a table of k slots in such a way that membership in A can be determined in a single probe. In his model it is assumed that all elements of A are physically stored in the table. If this assumption is relaxed and arbitrary elements in U can be stored in order to encode subsets A, then Yao's upper bound is no longer valid. It fails for trivial reasons only: a single probe lookup strategy only exists when it is possible to encode arbitrary subsets of U by a bitmap. Our second result is an improvement of the optimal program size for perfect hash functions, solving an open problem from Slot and Van Emde Boas (1984): For every value u, value k ≤ u, and every subset A of U = {0, ..., u - 1} there exists a perfect hash function F which scatters A completely into a hash table of size O(k), such that the program size of F is O(k·log log k + log log u) and the evaluation time of F is O(1). These estimates are expressed in standard RAM space and instructions respectively. This improves the O(k·log k + log log u) upper bound established by Mehlhorn (1984) and Slot and Van Emde Boas (1984). © 1986.
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine
Raymond Wu, Jie Lu
ITA Conference 2007
Elena Cabrio, Philipp Cimiano, et al.
CLEF 2013