Browse Prior Art Database

Key to Address Transformation System

IP.com Disclosure Number: IPCOM000094060D
Original Publication Date: 1966-May-01
Included in the Prior Art Database: 2005-Mar-06
Document File: 5 page(s) / 49K

Publishing Venue

IBM

Related People

Dunham, B: AUTHOR [+3]

Abstract

This relates to the problem of file memory organization. A vital aspect of this problem is that of obtaining an efficient procedure for performing key-to-address transformation. The latter problem, briefly posed, is this.

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 33% of the total text.

Page 1 of 5

Key to Address Transformation System

This relates to the problem of file memory organization. A vital aspect of this problem is that of obtaining an efficient procedure for performing key-to-address transformation. The latter problem, briefly posed, is this.

An item in the file consists of two parts. The identifier or key normally remains fixed and distinguishes the item from others in the file. The record is subject to variation and consists of the file data relevant to the particular item. The problem is to associate a memory address with each key, i.e., to define a transformation from keys to addresses.

The keys generally tend to be long strings of alphanumeric characters. The actual set of keys associated with a given file contain clusters of nearly identical strings sequenced alphabetically, numerically, or otherwise on various positions in the string. The number of actual keys is almost always far smaller than the total number of possible keys.

Whenever two or more keys map to the same address, some provision must be made for preserving the integrity of the records associated with these keys. All such records cannot be stored in the same memory location. Because such occurrences of overflow represent exceptions to the normal processing procedure, they result eventually in loss of time, and so are to be avoided or at least minimized.

The overflow characteristics expected to be obtained via some device or procedure are influenced strongly by the assumptions made about the problem. If an assumption is made as to precisely which elements of the key space comprise the key set, mapping can be effected under which each element in the set of addresses used has a unique pre-image in the key set. Such an assumption approximates the case in which the constituents of the key set of a file change slowly or not at all. The records can change as often as desired. It is additions to and deletions from the key set which are assumed to be infrequent.

There are many situations in which there is unwillingness or inability to assume there is complete knowledge of the key set. It may be that the file is one of a rapidly changing, in the above sense, nature, or that it is desired to achieve a general purpose mapping, one applicable to all key sets. In this case, a transformation must be arrived at whose domain is at least extendable to the entire set of possible keys. The assumptions made regarding the key set are now of a more general character, e.g., those of the existence and form of clusters. It is desirable that the general-purpose mapping achieved is as random as possible with regard to the key set assumptions employed. By this is meant that systematically chosen elements of the key set, as, for example, members of a cluster, are mapped to randomly chosen elements of the address space.

To reiterate, the object of a general-purpose transformation is, heuristically, to map systematically chosen elements of the key space into random elements of...