Grid file algorithms were suggested . . . to provide multi-key access to records in a dynamically growing file. We specify here two algorithms and derive the average sizes of the corresponding directories. . . . [We] give corresponding results for biased distributions and compare transient phases.

--From the Author’s Abstract

Grid File is a generic name for geometric algorithms used to map multiple-key indices onto primary files or databases. Two existing methods by other authors [1,2] are generalized to the multidimensional environment. The presence of a hashing function is the primary difference between the two algorithms; it is recommended to provide uniformity when presented with biased key distributions.

The paper’s organization is straightforward and clear. The first section is an introduction to grid file algorithms, while the second provides an analysis of their performance. The third section is an asymptotic analysis of performance; it is not for the mathematical dilettante. The fourth section compares the behavior of the two extended algorithms under both uniform and biased distributions. A brief conclusion provides recommendations for implementation of the two algorithms as a function of data condition.

The audience for this paper is limited. The paper is, however, a solid analytic work worthy of study by those interested in either the analysis of algorithms or the subject of multi-key access.