The Program Complexity of Searching a Table.

Abstract
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 (1+0(1)) 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 nk/2 to the k+1 power (1+0(1)) 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.

This publication has 0 references indexed in Scilit: