Information retrieval based on rank-ordered cumulative query scores calculated from weights of all keywords in an inverted index file for minimizing access to a main database

• US 5,263,159 A
• Filed: 09/18/1990
• Issued: 11/16/1993
• Est. Priority Date: 09/20/1989
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mitsui, Kinichi
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): WANG, PETER
• Application Number:
  US07/584,305
• Time in Patent Office: 1,155 Days
• Field of Search: 395/600, 364/DIG. 1, 364/DIG. 2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method and system are described for increasing quantitative database retrieval processing speed by minimizing access to the sequential file to the smallest possible value by use of score calculations using only the transposed file to rank the retrieval objects and terminating the process at a specified number of retrieval objects. Access to the transposed file is minimized by avoiding accessing unnecessary parts as much as possible, through the calculation of an anticipated score value which is used to make decisions about the optimum time for stopping the retrieval process. Further efficiencies are described through the use of relaxed order-ranking conditions which allow the process to be logically terminated even before the specified number of retrieval objects have been absolutely determined.

Claims

1. An information retrieval method for use in a computer having a processor, an external storage, a main memory into which data from the external storage can be copied, a sequential file stored in the external storage containing a plurality of retrieval objects, each retrieval object having a unique retrieval object identifier, a transposed file stored in the external storage in which access keys are associated with a set of retrieval object identifiers, and a query inputting device for specifying a query expressed as a combination of access keys given weighting coefficients and a number N of retrieval objects to be output, the information retrieval method comprising the steps of:

selecting, using the processor, an access key in the query having the highest weighting coefficient which has not been previously selected, responsive to the inputting of a query;

copying data into the main memory from the transposed file which contains the retrieval object identifiers which are associated with the selected access key;

calculating, using the processor, for each retrieval object identifier a cumulative query score by adding the weighting coefficient for the selected access key to a previously calculated cumulative query score, if any, for each retrieval object which contains the selected access key;

determining, using the processor, for each retrieval object a maximum anticipated score by adding the weighting coefficient for all access keys not previously selected to a previously calculated cumulative query score, if any, for each retrieval object identifier;

ranking, using the processor, the cumulative query scores for retrieval object identifiers from highest to lowest to create a rank list;

repeating the selecting, copying, calculating, determining and ranking steps until all access keys in the query have been selected or the cumulative query score at the N-th element in the rank list exceeds the maximum anticipated score for any retrieval object with a cumulative query score at the (N+1)-th element in the rank list or below; and

reading N retrieval objects corresponding to the N retrieval object identifiers having the highest cumulative query scores from the sequential file into the main memory.

2. An information retrieval method for use in a computer having a processor, an external storage, a main memory into which data from the external storage can be copied, a sequential file stored in the external storage containing a plurality of retrieval objects, each retrieval object having a unique retrieval object identifier, a transposed file stored in the external storage in which access keys are associated with a set of retrieval object identifiers and a query inputting device for specifying a query expressed as a combination of access keys given weighting coefficients and a number N of retrieval objects to be output, the information retrieval method comprising the steps of:

selecting, using the processor, an access key in the query having the highest weighting coefficient which has not been previously selected, responsive to the inputting of a query;

copying data into the main memory from the transposed file which contains the retrieval object identifiers which are associated with the selected access key;

calculating, using the processor, for each retrieval object identifier a cumulative query score by adding the weighting coefficient for the selected access key to a previously calculated cumulative query score, if any, for each retrieval object which contains the selected access key;

determining, using the processor, for each retrieval object a maximum anticipated score by adding the weighting coefficient for all access keys not previously selected to a previously calculated cumulative query score, if any, for each retrieval object identifier;

ranking, using the processor, the cumulative query scores for retrieval object identifiers from highest to lowest to create a rank list;

repeating the selecting, copying, calculating, determining and ranking steps until all access keys in the query have been selected or the cumulative query score at the N-th element in the rank list exceeds the maximum anticipated score for any retrieval object identifier with a cumulative query score at the (N+M)-th element in the rank list or below (where M is a pre-selected integer greater than

     2); and

reading the sequential file for N+M retrieval objects corresponding to the N+M retrieval object identifiers having the highest cumulative query scores from the sequential file into the main memory.

3. An information retrieval system having a processor, an external storage, a main memory into which data from the external storage can be copied, a sequential file stored in an external storage containing a plurality of retrieval objects, each retrieval object having a unique retrieval object identifier, a transposed file stored in the external storage in which access keys are associated with a set of retrieval object identifiers, and a query inputting device for specifying a query expressed as a combination of access keys given weighting coefficients and a number N of retrieval objects to be output, the information retrieval system comprising:

means for selecting, using the processor, from among the access keys which have not been previously selected, an access key in the query having the highest weighting coefficient, responsive to the inputting of a query;

means for copying data into the main memory from the transposed file which contains the retrieval object identifiers which are associated with the selected access key;

means for calculating, using the processor, a cumulative query score and a maximum anticipated score for each retrieval object identifier based on the query and the data copied from the transposed file, the cumulative query score being found by adding the weighting coefficient for the selected access key to a previously calculated cumulative query score, if any, and to zero if there is no previously calculated cumulative query score, for each retrieval object which contains the selected access key and the maximum anticipated score being found by adding the weighting coefficient for all access keys not previously selected to a previously calculated cumulative query score for each retrieval object identifier;

means for ranking, using the processor, the cumulative query scores for retrieval object identifiers from highest to lowest to form a rank list;

means for repeatedly activating the selecting, copying, calculating and ranking means until all access keys in the query have been selected or the cumulative query score at the N-th element of the rank list exceeds the maximum anticipated score for any retrieval object identifier with a cumulative query score at the (N+1)-th rank or below; and

means for reading the sequential file for N retrieval objects corresponding to the N retrieval object identifiers having the highest cumulative query scores.