February 1977 - Vol. 20 No. 2

Some recent work on the development of general-purpose computer-based statistical and data processing capabilities for handling multidimensional arrays of data is presented. Attention is first given to some of the general problems of multidimensional table and array processing. This is followed by a summary of some recent developments in array processing capabilities at the World Bank, in particular, the system identified as WRAPS (World Bank Retrieval and Array Processing System).

Static measurements of the list structure of five large Lisp programs are reported and analyzed in this paper. These measurements reveal substantial regularity, or predictability, among pointers to atoms and especially among pointers to lists. Pointers to atoms are found to obey, roughly, Zipf's law, which governs word frequencies in natural languages; pointers to lists usually point to a location physically nearby in memory. The use of such regularities in the space-efficient representation of list structure is discussed. Linearization of lists, whereby successive cdrs (or cars) are placed in consecutive memory locations whenever possible, greatly strengthens the observed regularity of list structure. It is shown that under some reasonable assumptions, the entropy or information content of a car-cdr pair in the programs measured is about 10 to 15 bits before linearization, and about 7 to 12 bits after.

The convex hulls of sets of n points in two and three dimensions can be determined with O(n log n) operations. The presented algorithms use the “divide and conquer” technique and recursively apply a merge procedure for two nonintersecting convex hulls. Since any convex hull algorithm requires at least O(n log n) operations, the time complexity of the proposed algorithms is optimal within a multiplicative constant.

Transient-free average working-set size and transient-free missing-page rate for a finite sample of a reference string are defined. Use of these statistics is appropriate if the contents of the working set at the start of the recorded string are unknown. If a certain stationarity condition holds, these statistics provide unbiased estimates of expected working-set sizes, missing-page probabilities, and interreference distance probabilities. Two other pairs of estimators are shown to be biased. Expressions for the transient-free statistics are obtained in terms of interval statistics. Several methods of computation are discussed, the usefulness of each depending on length of the sample, number of distinct references, and the amount of main storage available to the computer performing the calculations. In particular, methods are described for handling long strings containing many distinct page names.