The Complexity of Some Simple Retrieval Problems

Abstract

Four costs of a retrieval algorithm are the number of bits needed to store a representa- tion of a data base, the number of those bits which must be accessed to answer a retrieval question, the number of bits of state information required, and the logic complexity of the algorithm. Firm lower bounds are given to measures of the first three costs for simple binary retrieval problems. Systems are constructed which attain each bound separately. A system which finds the value of the kth bit in an N-bit string attains all bounds simultaneously. For two other more complex retrieval problems there are trading curves between storage and worst-case access, and between storage and average access. Lower and upper bounds to the trading curves are found. Minimal storage is a point of discontinuity on both curves, and for some complex problems large increases in storage are needed to approach minimal access. The cost of a complete updating algorithm is taken to be the number of bits it reads and/or writes in updating the representation of a data base. Lower bounds to mea- sures of this cost are cited. Optimal minimal-storage systems also have minimal update cost. Optimal minimal-access systems with large storage cost also have large update cost, but a small increase in storage for such a system may reduce update cost dramatically. KEY ~'ORDS AND PHRASES.' file, storage, retrieval, access, exact match, table lookup, computational complexity, retrieval algorithms, Kraft inequality