Boots – shoes – and leggings
Patent
1992-02-05
1992-09-08
Lee, Thomas C.
Boots, shoes, and leggings
3642282, 364229, 3642523, 3642821, 3642831, 3642834, 3642824, 3642822, 3642813, 3642817, 3642564, 3642531, 364DIG1, 364DIG2, G06F 706, G06F 708, G06F 714, G06F 736
Patent
active
051465906
ABSTRACT:
A fast method for sorting data in a distributed data processing system is disclosed. Each processor P.sub.1 12i locally sorts its data into a local sorted file S.sub.i 34i, simultaneously producing an index to the sorted data and a file of key data records R' 32 each comprising a key value paired with the processor's identifier. Each processor produces a distribution table DT.sub.i 28i of its key values using the index, and sends the table to acoordinator processor 18 which merges the processors' tables into a global distribution table GST 30. The global distribution table assigns subranges of key values to the processors, and is broadcast back to them. Each processor then sends each paired key value and processor identifier to the processor assigned by the global distribution table to handle the subrange containing that key value. The processors receive and merge the incoming key data records simultaneously as they send such pairs to other processors. An output stream V.sub.i 36i consisting only of processor identifiers is created by each processor from the merged key value and processor identifier pairs, and is sent to the host H 16, which merges it into a global output stream of processor identifiers. The processors simultaneously send their local sorted files S.sub.i to the host, which reads records from them in the order specified by the global output stream V.
REFERENCES:
patent: 4604686 (1986-08-01), Reiter et al.
patent: 4727509 (1988-02-01), Johnson et al.
patent: 4837735 (1989-06-01), Allen, Jr. et al.
patent: 4858146 (1989-08-01), Shebini
patent: 5006978 (1991-04-01), Neches
Dobosiewicz et al., "Sorting by Distributive Partitioning", Information Processing Letters, vol. 7, No. 1, pp. 1-6, Jan. 1978.
"The Art of Computer Programming", vol. 3, Sorting and Searching, pp. 99-105.
Janus, et al., "An Adaptive Method for Unknown Distributions in Distributive Partitioned Sorting", IEEE Transactions on Computers, vol. C-34, No. 4, pp. 367-372, Apr. 1985.
Teich et al., International Workshop, Database Machings, Munich, West Germany, 1983, pp. 206-226 (Springer-Verlag).
Menon, "A Study of Sort Algorithms for Multiprocessor Database Machines", Proceedings of the Twelfth International Conference on Very Large Data Bases, Kyoto, Aug. 1986, pp. 197-206.
Maekawa, "Parallel sort and join for high speed database machine operations", AFIPS National Compupter Conference, 1981, pp. 515-520.
Yuan-Chieh Chow, "Parallel Sorting in Local Computer Networks", (Int'l Journal of Mini & Microcomputers) vol. 7, No. 3, 1985, pp. 71-74, Anaheim, Calif.
X. Zhou et al., "Multi-selection and Distributed Sorting", (Proceedings of the 2nd Int'l Conf. on Computers and Applications), 23 Jun. 1987, pp. 490-493, Beijing, China.
K. V. S. Ramarao, "Distributed Sorting on Local Area Networks", (IEEE Transactions on Computers), vol. 37, No. 2, Feb. 1988, pp. 239-243, New York, N.Y.
M. Beck et al., "Design and Evaluation of a Parallel Sort Utility", (Proceedings of the 1986 Int'l Conference on Parallel & Distributed Processing), 19 Aug. 1986, pp. 934-941, Pennsylvania.
Lorie Raymond A.
Young Honesty C.
International Business Machines - Corporation
Lee Thomas C.
Pan Daniel H.
LandOfFree
Method for sorting using approximate key distribution in a distr does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for sorting using approximate key distribution in a distr, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for sorting using approximate key distribution in a distr will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-141733