The Program Complexity of Searching a Table.
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Given a fixed set S of n keys, we would like to store them so that queries of the form Does the point X belong to the set S can be answered quickly. A commonly employed scheme to solve this problem uses a table to store the keys, and a special purpose program depending on S which probes the table. We analyze the tradeoff between the maximum number of probes allowable to answer a query, and the information-theoretic complexity of the program to do so. Perfect hashing where the query must be answered in one probe has a program complexity of n times the log e to the base e 101 bits, and this lower bound can be achieved. Under a model combining perfect hashing and binary search methods, it is shown that for k probes to the table nk2 to the k1 power 101 bits are necessary and sufficient to describe a table searching algorithm. This model gives some information-theoretic bounds on the complexity of searching an external memory. Finally, we prove some lower bounds on the worst case performance of hash functions described by bounded Boolean circuits, and worst case performance of universal classes of hash functions.
- Theoretical Mathematics
- Computer Hardware