Storage schemes for boundedly extendible arrays

Abstract

The high costs of extendibility in array realizations can be reduced dramatically by placing a bound on how big the arrays of interest will grow. Whereas extendible array realizations require order of p · log p storage locations to store two-dimensional arrays having p or fewer positions, boundedly extendible array realizations (with a bound of p) can store these same arrays in precisely p locations. Moreover, boundedly extendible realizations can be designed to afford one additive traversal of both the rows and columns of the stored arrays, albeit at the cost of very inefficient storage utilization (order of p3/2 locations are needed to store arrays having p or fewer positions); extendible array realizations cannot yield such bidirectional additive traversal, irrespective of the price one is willing to pay. Moreover, if one can specify that the smallest array of interest is of shape h × w, then the p3/2 cost of storage utilization can be improved to roughly p · (p/hw)1/2 but no further. © 1977 Springer-Verlag.