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
Distribution Statement : APPROVED FOR PUBLIC RELEASE