Patent US6332871B1 successfully refreshed from Google Patents.
EP0127753A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Method for executing a distribution sort
Assignee: International Business Machines Corp
•
Filing: 1984-04-12
•
Granted: —
•
Expires: 2004-04-12
Abstract
Abstract A method for executing an external distribution sort in which the data to be rearranged includes keyed stored records that can be accessed on associative secondary storage. The method steps include random sampling of a certain number of keys and internally sorting the sampled keys (X<sub>1</sub>-X<sub>16</sub>): forming equal sized partitions of records in a single pass, each partition of which can fit within internal CPU memory and constitute a range of key values; and associatively retrieving all of the records whose keys lie within a range and internally sorting said records.
Inventors
- 👤 Eugene Emil Lindstrom
- 👤 Jeffrey Scott Vitter
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-03 00:53
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/24; G06F2207/00; G06F2207/22; G06F2207/222; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
119 words
A method for executing a distribution sort, the data to be rearranged including keyed records accessed by a CPU from associative secondary storage (15, 17, 19), the CPU having predetermined available internal memory, characterized by: random sampling of a plurality (S) of keys (X I -X I6 ) and internally sorting the sampled keys within the CPU; forming equal sized partitions of records in a single pass by obtaining a histogram of keys and ranges of key values and combining contiguous lesser populated ranges to form larger ranges such that each partition fits within the CPU internal memory; and associatively retrieving all of the records whose keys lie within a range of a partition and internally sorting said records.
Claim 2
Independent Claim
119 words
A method for executing a distribution sort, the data to be rearranged including keyed records accessed by a CPU from associative secondary storage (15, 17, 19), the CPU having predetermined available internal memory, characterized by: random sampling of a plurality (S) of keys (X I -X I6 ) and internally sorting the sampled keys within the CPU; forming equal sized partitions of records in a single pass by obtaining a histogram of keys and ranges of key values and combining contiguous lesser populated ranges to form larger ranges such that each partition fits within the CPU internal memory; and associatively retrieving all of the records whose keys lie within a range of a partition and internally sorting said records.
Claim 3
Dependent Claim
76 words
A method according to claim 1, wherein: the step of internal sorting said plurality of S sampled keys further includes the step of representing the sorted order by a sequential pointer list; the step of forming of partitions of records by obtaining a histogram of keys and ranges of key values includes for each key the step of performing a binary search on the pointer list in order to ascertain the range associated with the key.
Claim 4
Dependent Claim
65 words
A method according to claim 2, wherein the partition forming step further includes the steps of forming S+l ranges and denoting the sorted key values by X 1 , X 2 ,..., X S then for each value i from 1 to S+l, the ith range including the set of records whose key value lies in the semi-closed interval X i-1 to X i .
Claim 5
Dependent Claim
24 words
A method according to claim 1, wherein said method further includes the modification steps of marking selective records and associatively retrieving only marked records.
Claim 6
Dependent Claim
75 words
A method according to claim 1, wherein the step of forming partitions of records includes counting how many records belong to each range defined by the sorted sample key, and combining lesser populated contiguous ranges to form larger ranges, each range of which containing roughly the number of records that can fit within the internal memory, in order to estimate the distribution of key values of the records constituting a file in a single pass.
Claim 7
Dependent Claim
53 words
A method according to claim 5, wherein each record has a fixed length of R bytes and each key field consists of K less than R bytes, and further wherein any arbitrary file to be sorted consists of N records, and still further wherein the minimum amount of internal memory is proportional to
Claim 8
Dependent Claim
72 words
A method for executing an external distribution sort according to claim 1, wherein the step of random sampling of S keys includes the step of representing the sorted order by a sequential pointer list; and the step of forming equal sized partitions of records includes the step of performing a binary search on the pointer list in order to ascertain the range associated with the key for each key in the histogram.
Claim 9
Independent Claim
159 words
A method according to claims 1 and 7, wherein the step of forming of partitions of records includes the steps of processing each key on the associative device and performing a binary search on the pointer list in order to ascertain which small range contains the key, incrementing the count for that range by unity and storing the count for the range in the pointer fields of the key defining the upper limit of the range; the step of combining contiguous lesser populated ranges to form larger ranges includes the steps of combining small ranges so that the resulting combined range contains at most M/R records, in the event such combined range exceeds M/R, associating a special marker with the key that defines the upper limit of the range designating it as an overflow range, wherein M is the internal memory capacity in bytes of the CPU and R is the fixed length capacity in bytes of a record.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.