9406220 Coffey The problem of efficient real-time retrieval of information from large-scale databases is emerging as an important current application. This research will use a wide range of techniques derived from information theory to explore the fundamental limits of such retrieval systems. Many existing information theory research topics are directly related to the database problem, and the application in turn generates many novel fundamental problems in information theory. The basic underlying problem of context-dependent requests for information -- from a database whose physical structure does not match the user-perceived structure of the data -- is modeled as a novel type of random walk problem, in which one random walk (by the user over the data) drives a designed random walk by the system through the database. Results are derived which demonstrate that access time can be greatly improved in straightforward ways by adding redundancy. Potential extensions to systems in which highly compressible data is stored in databases with arbitrary structure, with more general forms of redundancy, are discussed. The theoretical results developed in this research will provide insight into the design of information retrieval systems appropriate for a variety of scientific applications. These theoretical results , however, can only provide first-order guidance in system design. Further guidance can be found by comparisons between the results derived from somewhat abstract models and those arrived at through more detailed simulation of systems. This research will investigate the applicability and robustness of the results of this researah and those of others to system design through system simulation. Actual datasets and realistic workloads can be used to validate the models and assess the applicability of the results to actual systems. ***
