Managing storage for extendible arrays

Abstract

Efficient storage utilization by schemes which allocate storage for extendible arrays is studied. A minimax lower bound on efficiency of storage use by such schemes is derived; and a scheme which achieves this bound is exhibited. When arrays are constrained to expand according to a preassigned finite set of shapes, the general lower bound can be lowered dramatically; in fact, if a single shape for expansion is chosen, one can devise a scheme which utilizes storage perfectly for arrays of that shape.