Accession Number : ADA135299

Title :   The Program Complexity of Searching a Table.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Mairson,H G

PDF Url : ADA135299

Report Date : Oct 1983

Pagination or Media Count : 17

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.

Descriptors :   *Information retrieval, *Searching, *Set theory, Memory devices, Problem solving, Theorems

Subject Categories : Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE