Browse Prior Art Database

high Record Access, First Then Closest Fit String Construction Method for a Set of File Blocks on Disk or Drum Storage

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

Publishing Venue

IBM

Related People

Conner, WM: AUTHOR [+2]

Abstract

The intermediate and output phases of a sort program merge strings of ordered records, which are grouped in blocks on the sort's workfile to decrease the access time and storage requirement. In a conventional merge the block sequence of any string merged is identical to the block sequence of a previously distributed string, even though this restriction is unnecessary for disk and drum workfiles. Algorithm HFC which is the figure eliminates this unnecessary restriction, and assigns each workfile block to one of strings S(1),S(2),...,S(n) without regard to the prior distribution order.

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 69% of the total text.

Page 1 of 2

high Record Access, First Then Closest Fit String Construction Method for a Set of File Blocks on Disk or Drum Storage

The intermediate and output phases of a sort program merge strings of ordered records, which are grouped in blocks on the sort's workfile to decrease the access time and storage requirement. In a conventional merge the block sequence of any string merged is identical to the block sequence of a previously distributed string, even though this restriction is unnecessary for disk and drum workfiles. Algorithm HFC which is the figure eliminates this unnecessary restriction, and assigns each workfile block to one of strings S(1),S(2),...,S(n) without regard to the prior distribution order.

Algorithm HFC uses a function p(j) defined as follows, where m is the merge capacity.
1. If the size of the largest set of mutually overlapping

blocks in the file does not exceed

m, then p(j) = m-1 for 1 </- j </- m.
2. Otherwise, p(j) = m-1 for 1 </- j </- m-1, and p(j) =

m-1+m[j/m]

for j >/- m.

Note that when case 2 applies, p(1) = p(2) = ... = p(m-1) = m-1, and for 1> 0, p(im) = p(im+1) = ... + p(im+m-1) = im+m-1.

The sum of the lengths of the strings S(1),S(2),...,S(m-1) found by algorithm HFC is the theoretical maximum for the file. Moreover, for i > 0, the sum of the lengths of the strings S(im),S(im+1),..., S(min[im+m-1,n]) is a theoretical maximum for a file consisting of the blocks on S(im),...,S(n). Therefore, a merge strategy which executes algorithm HFC p...