Browse Prior Art Database

Reserve Strings Merge Strategy

IP.com Disclosure Number: IPCOM000082039D
Original Publication Date: 1974-Sep-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 44K

Publishing Venue

IBM

Related People

Conner, WM: AUTHOR [+2]

Abstract

A sort employing a conventional merge strategy always merges strings, which are distributed either by the input phase of the sort or by a prior merge operation. When these strings can be directly accessed on disks or drums, an optimal conventional merge strategy can be constructed, based on Huffman's minimum redundancy encoding method (see D. E. Knuth, "Sorting and Searching," The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973).

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 66% of the total text.

Page 1 of 2

Reserve Strings Merge Strategy

A sort employing a conventional merge strategy always merges strings, which are distributed either by the input phase of the sort or by a prior merge operation. When these strings can be directly accessed on disks or drums, an optimal conventional merge strategy can be constructed, based on Huffman's minimum redundancy encoding method (see D. E. Knuth, "Sorting and Searching," The Art of Computer Programming, Vol. 3, Addison-Wesley, 1973).

In practice, the records that make up the strings are stored in blocks on the direct-access workfile devices, since this normally decreases their storage requirement and access time. The Reserve Merge Strategy (RMS) depicted in the figure takes advantage of the fact that these blocks can be accessed directly - the RMS merges strings constructed from workfile blocks without regard to prior distribution patterns. With an appropriate string construction method (used in the partition step marked with an asterisk in the figure), RMS is likely to sort a file with fewer block accesses than an optimal conventional strategy.

The partition step in RMS should assign blocks to strings S(1), S(2),...,S(n) in such a way that for any string S(im), where m is the merge order and i > 0, it is more efficient to merge S(im) than to merge any lower numbered string. Either of the following criteria can produce this condition:
1. The sum of the lengths of S(1),S(2),...S(m1) is maximized

for the total file, and for i >...