An Analysis of Optimal Retrieval Systems with Updates.
MASSACHUSETTS INST OF TECH CAMBRIDGE RESEARCH LAB OF ELECTRONICS
Pagination or Media Count:
The performance of computer-implemented systems for data storage, retrieval, and update is investigated. A data structure is modeled by a set D d sub 1, d sub 2,...d subabsolute value of D of data bases. A set of questions Lambda lambda sub 1, lambda sub 2,...,lambda sub n about any d an element of D may be answered. A memory that is bit-addressable by an algorithm or an automaton models a computer. A retrieval system is composed of a particular mapping of data bases onto memory representations and a particular algorithm or automaton. By accessing bits of memory the algorithm can answer any lambda an element of Lambda about the d represented in memory and can update memory to represent a new d an element of D. Lower bounds are derived for the performance measures of storage efficiency, retrieval efficiency, and update efficiency. The minima are simultaneously attainable by a retrieval system for some data structures of interest. trading relations between the measures exist for other data structures.
- Information Science
- Computer Hardware