Method and apparatus for parallel sorting using parallel selection/partitioning
US6427148B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Nov 9, 1998 |
| Grant date | Jul 30, 2002 |
| Priority date | — |
| Expiry date | Nov 9, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An embodiment of the present invention provides a method and apparatus for sorting very large data sets using a parallel merge sort. Given sorted work files S1, . . . , Sp, produced by P processes, the described embodiment of the method effectively implements a parallel merge onto respective output partitions O1, . . . , Op of the processes P. Because each of these output partitions O has a finite size, the invention must quickly determine “splitting keys” for each output partition O in such a way that the data in the work files will be split between the multiple output partitions O without overrunning the size of any of the partitions O. Once the splitting keys for each partition are determined, the processes exchange data so that the output partitions of each process contains data between the splitting keys associated with that output partition.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.