Browse Prior Art Database

"Noisy Sort" - a Table Look-Up Method of Sorting Data Classes

IP.com Disclosure Number: IPCOM000037374D
Original Publication Date: 1989-Dec-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 43K

Publishing Venue

IBM

Related People

Horiguchi, S: AUTHOR [+2]

Abstract

A technique is described whereby a memory intensive method of sorting data classes, termed "Noisy Sort", is implemented when data to be sorted is represented by model data where the sort is known, as used in parallel computer processing. A table look-up method of sorting is employed, consisting of representations of the model data and permutation sequences which sort them.

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

Page 1 of 3

"Noisy Sort" - a Table Look-Up Method of Sorting Data Classes

A technique is described whereby a memory intensive method of sorting data classes, termed "Noisy Sort", is implemented when data to be sorted is represented by model data where the sort is known, as used in parallel computer processing. A table look-up method of sorting is employed, consisting of representations of the model data and permutation sequences which sort them.

The term "Noisy-Sort" is used because the concept does not always give a complete sort without the implementation of post-processing steps. Post- processing is accomplished by implementing typical standard sorting techniques, such as bubble sort.

"Noisy Sort" consists of two embodiments: a) an associative memory which allows the simultaneous reference to all stored data and external multiple data, and b) any memory device which furnishes the function of the associative memory for the particular sorting applications involved.

The "Noisy Sort" embodiments consist of three basic steps: Pre- processing; Table Look-up; and Post Processing. The concept considers a framework, where a sample of an actual data set to be sorted is approximately represented by a standard, or model data set. A table is then composed (preprocessing), using this model data set.

The "Noisy Sort" process implementation is as follows: Let x be a list of N real numbers to be sorted. Consider x to be a column vector in RN, and let CP(x) be the collection of N! vectors, the permutations of x taken in some order. CP(x) will also denote the N x N! matrix composed of these vectors, in that order, as columns. Let y be the vector of integers (1,2,...,N)T . Then the columns of CP(y) represent the collection of destination addresses into which the columns of CP(x) should be stored by sorting. Let X=(x1, x2,...,xN) be a sorted list of data, and let X=CP(x). Let Y=CP(y). The column yi in Y is the destination address and is set into the specific xi in X to be stored by sorting. Sorting is a mapping t:CP(x) T CP(y). Equivalently, t is a mapping of {xi}1N! into {yi}1N!, yi=t(xi), i=1,2,...,N!. There exists an N x N matrix M such that yl=Mxi, i=1,2,...,N!, in the sense of least squares [*]. That is, M solv...