Browse Prior Art Database

Storing Extendible Arrays By Hyperbolic Shells

IP.com Disclosure Number: IPCOM000081054D
Original Publication Date: 1974-Mar-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 2 page(s) / 44K

Publishing Venue

IBM

Related People

Rosenberg, AL: AUTHOR

Abstract

The above flowcharts illustrate an algorithm for allocating storage for extendible 2-dimensional arrays. The method uses materially less storage, in a minimax sense, than does any known competitor. An allocation scheme for arrays is viewed as a function DISPLACEMENT which maps array positions (ordered pairs of positive integers) onto positive integers: For a given array A, position A(I,J) is mapped onto location A-1 DISPLACEMENT (I,J). The allocation scheme is termed extendible if the function DISPLACEMENT is independent of the potential range of values of I and J. Thus, familiar store-by-row and store-by-column schemes are not extendible.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 2

Storing Extendible Arrays By Hyperbolic Shells

The above flowcharts illustrate an algorithm for allocating storage for extendible 2-dimensional arrays. The method uses materially less storage, in a minimax sense, than does any known competitor. An allocation scheme for arrays is viewed as a function DISPLACEMENT which maps array positions (ordered pairs of positive integers) onto positive integers: For a given array A, position A(I,J) is mapped onto location A-1 DISPLACEMENT (I,J). The allocation scheme is termed extendible if the function DISPLACEMENT is independent of the potential range of values of I and J. Thus, familiar store-by-row and store-by- column schemes are not extendible.

All known extendible allocation schemes have the property that, for infinitely many values I,J, DISPLACEMENT (I,J) >/= (I.J)/2/. An M x N matrix stored using such schemes may have large gaps since its M.N positions may be spread over
(M.N)/2/ locations. The allocation scheme described here has the property that, for all I and J, DISPLACEMENT (I,J) </= (I x J) x log/2/ (I x J). Thus, while known schemes may allocate storage better than the present scheme for arrays of particular shapes (such as the cubic shell technique [ref. 2]), the present technique is dramatically superior to all known schemes in a minimax sense.

The described scheme allocates storage by shells [ref. 1], specifically by hyperbolic shells. (Each shell comprises all ordered pairs of integers with the same product...