US5440734A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for MSD radix sort bin storage management
Assignee: International Business Machines Corp
•
Filing: 1993-09-14
•
Granted: 1995-08-08
•
Expires: 2013-09-14
Abstract
Abstract A system and process for enhancing internal radix sorting bin storage efficiency by using linked blocks of contiguous storage space while controlling the number of partially-filled blocks required. The improved internal radix sorting procedure makes it possible to sort large computer files very efficiently without the risk of overflowing allocated storage space. A Most Significant Byte (MSD) radix sorting procedure avoids the collection step required in the LSD radix sorting procedure. The distribution pass is halted whenever a bin is found to contain less than a predetermined threshold number of records and the bin is then sorted immediately using a simple comparison-based sort. At each distribution rank, the system selects and sorts the smallest bins first, thereby quickly releasing storage blocks that may be required during the distribution sort passes for the larger bins. In this radix sorting procedure, the total number of linked storage blocks of size B can never exceed (R/B)+(1-1/B)A, where R is the total number of records to be sorted and A=(M-1) log M (R/T)+min (T,M)+1, where M=key field digit radix and T=bin size threshold for switching to comparison-based sort completion.
Inventors
- 👤 Bruce A. Wagar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 21:25
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/24; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
190 words
A computer-implemented method for sorting a plurality R of records according to their key fields, each said key field having a plurality D of digits of radix M, wherein R, D and M are non-zero positive integers, said method comprising the steps of: (a) recursively distributing and collecting a group of representations of said key fields, each recursion including the ordered steps of (a.1) comparing each of said group of key fields against an extrinsic attribute and assigning said each key field to one of a plurality M of same-attribute subgroups, (a.2) assigning to each said same-attribute subgroup a bin count index representing the number of said plurality R of records having key fields that are smaller than the minimum said key field in said each same-attribute subgroup, and (a.3) sorting and moving the sorted key fields from each said same-attribute subgroup having a size less than a predetermined threshold T to a predetermined location in an output storage area, where said predetermined location corresponds to said bin count index and T is a non-zero positive integer; and (b) repeating said each recursion for the remaining undistributed said same-attribute subgroups.
Claim 2
Dependent Claim
190 words
A computer-implemented method for sorting a plurality R of records according to their key fields, each said key field having a plurality D of digits of radix M, wherein R, D and M are non-zero positive integers, said method comprising the steps of: (a) recursively distributing and collecting a group of representations of said key fields, each recursion including the ordered steps of (a.1) comparing each of said group of key fields against an extrinsic attribute and assigning said each key field to one of a plurality M of same-attribute subgroups, (a.2) assigning to each said same-attribute subgroup a bin count index representing the number of said plurality R of records having key fields that are smaller than the minimum said key field in said each same-attribute subgroup, and (a.3) sorting and moving the sorted key fields from each said same-attribute subgroup having a size less than a predetermined threshold T to a predetermined location in an output storage area, where said predetermined location corresponds to said bin count index and T is a non-zero positive integer; and (b) repeating said each recursion for the remaining undistributed said same-attribute subgroups.
Claim 3
Dependent Claim
75 words
The method of claim 1 wherein each said group and said subgroup of key field representations is stored in a unique bin in a data storage means, each said bin having a linked list of one or more storage blocks only one of which is not filled, each said storage block having contiguous memory space for up to a plurality B of said key field representations, where B is a positive integer greater than unity.
Claim 4
Dependent Claim
24 words
The method of claim 2 wherein said storage blocks are linked and released responsive to changes in the undistributed contents of said each bin.
Claim 5
Dependent Claim
28 words
The method of claim 3 wherein said extrinsic attribute for each said recursion is the most significant said key field digit remaining uncompared from all previous said recursions.
Claim 6
Dependent Claim
21 words
The method of claim 4 wherein said repeating step (b) is first performed on the smallest said remaining undistributed same-attribute subgroup.
Claim 7
Dependent Claim
20 words
The method of claim 4 wherein said repeating step (b) is first performed on the smallest said remaining same-attribute subgroup.
Claim 8
Dependent Claim
20 words
The method of claim 1 wherein said repeating step (b) is first performed on the smallest said remaining same-attribute subgroup.
Claim 9
Dependent Claim
28 words
The method of claim 1 wherein said extrinsic attribute for each said recursion is the most significant said key field digit remaining uncompared from all previous said recursions.
Claim 10
Independent Claim
203 words
A system for sorting a plurality R of records according to their key fields, each said key field having a plurality D of digits of radix M, wherein R, D and M are non-zero positive integers, said system comprising: bin storage means for storing groups of representations of said key fields; output storage means for storing said records in key field order; distributing means coupled to said bin storage means for comparing each of a group of said key fields against an extrinsic attribute and for assigning each key field to one of a plurality M of same-attribute subgroups; counting means coupled to said distributing means for assigning to each said same-attribute subgroup a bin count index representing the number of said plurality R of records having key fields that are smaller than the minimum said key field in said each same-attribute subgroup; and threshold sorting means coupled to said bin storage means for first sorting and moving the sorted key field representations from each said same-attribute subgroup having a size less than a predetermined threshold T to a predetermined location in said output storage means, where said predetermined location corresponds to said bin count index and T is a non-zero positive integer.
Claim 11
Independent Claim
203 words
A system for sorting a plurality R of records according to their key fields, each said key field having a plurality D of digits of radix M, wherein R, D and M are non-zero positive integers, said system comprising: bin storage means for storing groups of representations of said key fields; output storage means for storing said records in key field order; distributing means coupled to said bin storage means for comparing each of a group of said key fields against an extrinsic attribute and for assigning each key field to one of a plurality M of same-attribute subgroups; counting means coupled to said distributing means for assigning to each said same-attribute subgroup a bin count index representing the number of said plurality R of records having key fields that are smaller than the minimum said key field in said each same-attribute subgroup; and threshold sorting means coupled to said bin storage means for first sorting and moving the sorted key field representations from each said same-attribute subgroup having a size less than a predetermined threshold T to a predetermined location in said output storage means, where said predetermined location corresponds to said bin count index and T is a non-zero positive integer.
Claim 12
Dependent Claim
65 words
The system of claim 9 further comprising: a plurality of bins in said bin storage means, each said bin having a linked list of one or more blocks of contiguous storage space only one of which is not filled, each said block having contiguous space for up to a plurality B of said key field representations, where B is a positive integer greater than unity.
Claim 13
Dependent Claim
41 words
The system of claim 10 further comprising: bin management means coupled to said bin storage means for linking and releasing said blocks of storage contiguous space to any said bin responsive to changes in the undistributed contents of said any bin.
Claim 14
Dependent Claim
22 words
The system of claim 11 wherein said extrinsic attribute is the most significant said key field digit remaining uncompared from previous distributions.
Claim 15
Dependent Claim
23 words
The system of claim 12 further comprising: bin ordering means coupled to said bin storage means for ordering said same-attribute subgroups by size.
Claim 16
Dependent Claim
23 words
The system of claim 12 further comprising: bin ordering means coupled to said bin storage means for ordering said same-attribute subgroups by size.
Claim 17
Dependent Claim
23 words
The system of claim 9 further comprising: bin ordering means coupled to said bin storage means for ordering said same-attributes subgroups by size.
Claim 18
Dependent Claim
22 words
The system of claim 9 wherein said extrinsic attribute is the most significant said key field digit remaining uncompared from previous distributions.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-07 | 1999-02-06 | 1999-08-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-07 | 2003-02-06 | 2003-08-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-07 | 2007-02-06 | 2007-08-08 | $7700.00 | Window Closed / Lapsed |