Browse Prior Art Database

Transformation for Information Retrieval and Sorting

IP.com Disclosure Number: IPCOM000092065D
Original Publication Date: 1968-Aug-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Ghosh, SP: AUTHOR [+2]

Abstract

A key transformation algorithm is used to transform the input record to be stored into an address in the memory at which the record is stored. The transformation is based not only on the particular record to be stored, but upon the records in the entire set which are to be stored. The transformation allows the mapping of the records, expressed in binary notation, into the minimum possible number of addresses without overlapping. Thus, for example, if there are N records to be stored, the information in these records is mapped into N addresses, one for each record 0, 1...N-1. The length of each address is equal to X, where X = log(2)N, regardless of the length of records.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 64% of the total text.

Page 1 of 1

Transformation for Information Retrieval and Sorting

A key transformation algorithm is used to transform the input record to be stored into an address in the memory at which the record is stored. The transformation is based not only on the particular record to be stored, but upon the records in the entire set which are to be stored. The transformation allows the mapping of the records, expressed in binary notation, into the minimum possible number of addresses without overlapping. Thus, for example, if there are N records to be stored, the information in these records is mapped into N addresses, one for each record 0, 1...N-1. The length of each address is equal to X, where X = log(2)N, regardless of the length of records.

Assume a record in a set of records is to be stored, and V is the set of records N is the number of records in the set n is the number of positions in each record v is the record to be stored and is expressed as (a(1), a(2), a(3)...a(n)).

h (a(1), a(2)..a(m-1), a(m)) is the number of vectors in the set V whose first coordinate is equal to a(1) of v, second coordinate is equal to a2 of v...m-1 the coordinate is equal to a (m-1) of v, and mth coordinate is not equal to a of v. m is a variable denoting a particular position in the record.

The algorithm for computing an address for the record (v) is given by

This algorithm can be used for mapping in information retrieval. Since it results in an ordered sequence depending on the values of the record...