Parallel merge and sort process method and system thereof

Details Parallel merge and sort process method and system thereof Parallel merge and sort process method and system thereof

1994-10-12

1997-06-17

Black, Thomas G.

395675, 395800, G06F 1730

Patent

active

056405545

ABSTRACT:
When a list to be sorted is divided into L sorted merge objective lists, each of the merge objective lists is formed of a plurality of blocks (where L is any natural number larger than or equal to 2). For each block, a block information record having a block identifier and a key value of a representative record of the block is generated. With the block information records, a first auxiliary information list is generated. The first auxiliary information list is sorted in a predetermined order of key values so as to generate a second auxiliary information list. The second auxiliary information list is almost equally divided into P portions (where P is any natural number larger than or equal to 2). For each of the P sub-auxiliary information lists, a forward boundary value and a backward boundary value are set corresponding to a predetermined rule. The P sub-auxiliary information lists are allocated to P process units. Each of the P process units retrieves a portion (segment) corresponding to the sub-auxiliary information list from the L sorted merge objective lists and merges blocks of the segment.

REFERENCES:
patent: 5179699 (1993-01-01), Iyer et al.
patent: 5265260 (1993-11-01), Hendricks
patent: 5386583 (1995-01-01), Hendricks
Beck et al., "Sorting Large Files on a Backend Multiprocessor", IEEE Transactions on Computers, vol. 37, No. 7, Jul., 1988, pp. 769-778.
Guang-Sheen Liu et al., "Parallel Merge Module for Combining Sorted Lists", IEE Proceedings E (Computers and Digital Techniques); vol. 136, No. 3, May 1989, pp. 161-165.
Iyer et al., "System Issues in Parallel Sorting for DatabaseSystems", Sixth International Conference on Data Engineering, 5-9 Feb. 1990, pp. 246-255.
Varman et al., "An Efficient Multiprocessor Merge Algorithm", PARBASE-90, International Conference on Databases, ParallelArchitectures and Their Applications, 7-9 Mar. 1990, Miami beach Florida, pp. 276-283.
Guan et al., "Time-Space Optimal Parallel Merging and Sorting", IEEE Transactions on Computers, vol. 40, No. 5, May 1991, pp. 596-602.
Kelley McTiernan, "An end to the Mystery of Sorting, When You Can't Fit Every Element in Memory, Turn to This Algorithm", Computer Language, vol. 8, No. 7, Jul., 1991 pp. 57-69.
DeWitt et al., "Parallel Database Systems: The Future of High Performance Database Systems", Communications of the ACM, vol. 35, No. 6, Jun. 1992, pp. 85-98.
Liszka et al., "A Modulo Merge Sorting Network", Fourth Symposiumon the Frontiers of Massively Parallel Computation, 19-21 Oct. 1992, Los Alamitos, California, pp. 164-169.

Affiliated with

Also associated with

Rating

Parallel merge and sort process method and system thereof does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallel merge and sort process method and system thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel merge and sort process method and system thereof will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2165417