System for MSD radix sort bin storage management

Details System for MSD radix sort bin storage management System for MSD radix sort bin storage management

1993-09-14

1995-08-08

Black, Thomas G.

Boots, shoes, and leggings

364DIG1, 3642229, G06F 706, G06F 722, G06F 724

Patent

active

054407346

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.sub.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.

REFERENCES:
patent: 4210961 (1980-07-01), Whitlow
patent: 4809158 (1989-02-01), McCauley
patent: 5218700 (1993-06-01), Beechick
patent: 5396622 (1995-03-01), Lee et al.

Affiliated with

Also associated with

Rating

System for MSD radix sort bin storage management does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for MSD radix sort bin storage management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for MSD radix sort bin storage management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-978571