Browse Prior Art Database

Worst Record Check

IP.com Disclosure Number: IPCOM000048710D
Original Publication Date: 1982-Mar-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Ma, RK: AUTHOR [+3]

Abstract

A bit block algorithm has been developed to efficiently sort a file where there is limited work space and only a subset of the file fits into memory and it is not possible to write back into the file. According to this algorithm, the total number of records in the file is divided by the total number of bits available for mapping. A bit is set on as the records are searched sequentially, and any record represented by the bit is determined to qualify. At the same time, qualifying records are sorted into a limited work space called a bucket. If the bucket fills before all records are examined, then records are swapped in and out of the bucket until only the top records remain and all records have been examined. The problem is how to insert records into the bucket.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 1

Worst Record Check

A bit block algorithm has been developed to efficiently sort a file where there is limited work space and only a subset of the file fits into memory and it is not possible to write back into the file. According to this algorithm, the total number of records in the file is divided by the total number of bits available for mapping. A bit is set on as the records are searched sequentially, and any record represented by the bit is determined to qualify. At the same time, qualifying records are sorted into a limited work space called a bucket. If the bucket fills before all records are examined, then records are swapped in and out of the bucket until only the top records remain and all records have been examined. The problem is how to insert records into the bucket.

When determining the sort order of records in a file, a check is performed to see if the record in question is better than the worst record already collected in the sort bucket. If this is true, a binary search results. This check gives a fast, efficient resolution to the relative ordering of records.

1