Data processing: database and file management or data structures – Database design – Data structure types
Patent
1997-12-17
2000-05-16
Kulik, Paul V.
Data processing: database and file management or data structures
Database design
Data structure types
707 1, 707 2, 39580036, G05F 1730
Patent
active
060650052
ABSTRACT:
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.
REFERENCES:
patent: 4575798 (1986-03-01), Lindstrom et al.
patent: 5146590 (1992-09-01), Lorie et al.
patent: 5396622 (1995-03-01), Lee et al.
patent: 5579515 (1996-11-01), Hintz et al.
patent: 5724600 (1998-03-01), Ogiq
patent: 5822748 (1998-10-01), Cohen et al.
patent: 5826262 (1998-10-01), Bui et al.
Suehiro et al. "Integer Sorting on Shared-Memory Vector Parallel Computers" ICS 98, ACM Website, pp. 313-320, Jul. 1998.
Dusseau et al. "Fast Parallel Sorting Under LogP: Experience with the CM-5" IEEE Transactions on Parallel and Distributed Systems, vol. 7, No. 8, pp. 791-805, Aug. 1996.
Mueck et al. "Optimizing Sort Order Query Execution in Balanced and Nested Grid Files" IEEE Transactions on Knowledge and Data Engineering, vol. 7, No. 2, pp. 246-260, Apr. 1995.
Gal Shmuel
Hartmann Alan
Keren Mila
Marberg John M.
Sheinwald Dafna
International Business Machines - Corporation
Klein Esther E.
Krall Noreen A.
Kulik Paul V.
Wallace, Jr. Michael J.
LandOfFree
Data sorting does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data sorting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data sorting will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-268015