International Business Machines Corporation

Shmuel Gal

Zvi Yosef Yehudai

Dafna Sheinwald

Oded Cohn

Mila Keren

John M Marberg

Igal Galperin

Alan Hartmann

Yona Hollander

A method is described for operating a data processing system having a plurality of processors to sort a set of data records each having an associated key for governing the sort process. The method comprises determining a range for the key values by sampling the key values. The range is divided into a plurality of quantiles, one for each processor, each quantile having a respective index. At each processor, a plurality of buckets are defined, each bucket corresponding to a respective one of a plurality M.sub.p of subintervals in the quantile, each subinterval having a respective index. The index of the quantile in which the key value lies and the index of the subinterval in which the key value lies are determined directly from the key values using fast operations. Each key is distributed to the processor corresponding to the quantile in which the key value lies. At each processor, the keys falling in the quantile corresponding to the processor are distributed into the buckets according to the indices of the subintervals in which the key values lie, the buckets being processed in sequence in order to sort the records and the keys in each bucket sorted if the bucket contains more than one key. Finally, the sorted keys from each processor are concatenated.

Data sorting

A method is described for operating a computer to sort a set of data records each having an associated key for governing the sort process, the method comprising determining a range for the key values by sampling the key values; defining a plurality of buckets, each bucket corresponding to a respective one of a plurality M of subintervals in the range, and two edge buckets for key values outside the range, each subinterval having a respective index; distributing the keys among the buckets by determining directly from each key value the index of the subinterval into which the key value falls; and processing the buckets in sequence in order to sort the records, sorting the keys in each bucket if the bucket contains more than one key.

System and method for sorting data in a computer system using edge

A computer implemented method for speeding up the recursive most significant digit radix sorting of a set of record keys in which the keys are scanned for a shared or common prefix, coded according to the point in the key where they differ and the value of the differing digit, and processed such that during each dispersion phase the code words are used to speed processing by avoiding comparison matching of the prefixes, the recursive dispersion and collection phases continuing until singletons are reached. In the absence of shared prefixes the keys are normally recursively radix sorted.

Radix sorting method and means for minimizing movement of elements

Growing community of inventors

Haifa, Israel

Shmuel Gal