Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Reducing Search Time For Futile Searches

IP.com Disclosure Number: IPCOM000078160D
Original Publication Date: 1972-Nov-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Abstract

This is a method for reducing the time required for futile searches. Background.

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

Page 1 of 2

Reducing Search Time For Futile Searches

This is a method for reducing the time required for futile searches. Background.

There is a growing number of computer application situations where a file may be searched to determine whether a particular record is included. In some cases, the probability is high that there will be no record found (NRF). Examples of such situations include: Police "wanted" files. Most interrogation of the file will

yield NRF for the person or auto being detained by police in a

patrol car.

Checking to determine whether a certain person is cleared as a

security risk or credit risk.

Determining whether a certain missing person has been

hospitalized.

Determining which airline flight a certain passenger is on.

Determining whether an accident victim is registered as a diabetic.

The conventional way to determine whether a particular record is included in a file, is to look either where the record would be stored or where it would be indexed. If that search is futile, the NRF condition is declared. The technique described here significantly reduces search-time for searches which turn out to be futile, with only modest increase in search-time for searches that turn out to be successful. Principle.

In any file, presence or absence of a record with a partiiular key can be indicated, by a single bit whose position in a bit string is related to the key in a fixed pseudorandom way. Whenever one wants to determine whether a particular record is in the file, the appropriate bit can be checked. If that bit is off, the desired record is definitely not in the file. If the bit is on, there is high probability that the desired record is...