Browse Prior Art Database

Information Retrieval Technique

IP.com Disclosure Number: IPCOM000080415D
Original Publication Date: 1973-Dec-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Anglin, MD: AUTHOR [+6]

Abstract

Information retrieval applications frequently require exhaustive searching of large files to select qualified records. The technique described here reduces the search by eliminating from that search most of the records that will not qualify.

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

Page 1 of 1

Information Retrieval Technique

Information retrieval applications frequently require exhaustive searching of large files to select qualified records. The technique described here reduces the search by eliminating from that search most of the records that will not qualify.

Assume a file of v records of identical format, each containing k fields of data. The following steps must be accomplished in advance of accepting information- retrieval requests: 1. For every field of every record, calculate a hashed value (v) ij where i is record number and j is field number. In all cases, 0 </- (v) ij < m where m is a fixed value larger than k. Typically, m might be chosen such that m is approximately 100 times k. Mashing can be done by any reliable method such as divide by a fixed prime number. These hashed values are used to construct matrix B as described below, when B has been constructed, the hashed values can be discarded. 2. Construct a matrix B of binary bits (b) pq where (b) pq = 1 if, and only if, for i = q, there exists a (v) ij whose value is p. B will be a m by n bit-matrix. (Matrix B can be constructed by sorting the (v) ij on major field i and minor field v.) Matrix B should be stored such that each row is a logical record.

Assume there is a requirement to retrieve any and all records having field values satisfying Boolean condition F. For example, F might specify: Field 3 = (value 1) and Field 8 = (value 2) or Field 1 = (value 3) and Field 11 = (value 4). To...