An Analysis of Optimal Retrieval Systems with Updates.
Abstract
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 sub/absolute 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1975
- Accession Number
- ADA012308
Entities
People
- Richard A. Flower
Organizations
- Massachusetts Institute of Technology