Preserving Average Proximity in Arrays.
Abstract
The combinatorial problem of storage arrays as various kinds of list structures is examined. Embeddings of graphs are used to model the loss of proximity involved in such storage schemes, and an elementary proof that arrays cannot be stored as linear lists with bounded loss of proximity is presented. Average loss of proximity is then considered, and it is shown that arrays cannot be stored as linear lists with only bounded loss of average proximity, but can be so stored in binary trees. The former result implies that row major order is an asymptotically optimal storage strategy for arrays. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 10, 1976
- Accession Number
- ADA027360
Entities
People
- Richard A. Demillo
- Richard J. Lipton
- Stanley C. Eisenstat
Organizations
- University of Wisconsin–Milwaukee