Accession Number:

ADA058477

Title:

Preserving Average Proximity in Arrays with Duplications.

Descriptive Note:

Master's thesis,

Corporate Author:

ILLINOIS UNIV AT URBANA-CHAMPAIGN APPLIED COMPUTATION THEORY GROUP

Personal Author(s):

Report Date:

1978-04-01

Pagination or Media Count:

64.0

Abstract:

Efficiency of storage management in algorithms which use arrays is often enhanced if the arrays are stored in a proximity-preserving manner, that is, array positions which are close to one another in the array are also stored close to one another in the memory structure. It has been shown that any scheme that stores arrays in a linear memory, in both the worst and the average case, induces unbounded loss of proximity, but arrays can be stored in binary trees with bounded loss of average proximity. This paper is devoted to studying the effect of introducing duplication of items of a square array A on the average path length between the images of any two records adjacent to A under mapping from A into the set of leaves of a complete binary tree. It is shown that with the appropriate choice of duplications, in some arrays the average path length can be decreased by as much as 12 without using a deeper tree than needed in the absence of duplication. Author

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE