Adaptive evaluation of text search queries with blackbox scoring functions

• US 7,991,771 B2
• Filed: 11/21/2006
• Issued: 08/02/2011
• Est. Priority Date: 05/30/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rajagopalan, Sridhar, Lyle, Robert W., Beyer, Kevin Scott, Shekita, Eugene J.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Singh; Amresh
• Application Number:
  US11/561,949
• Publication Number:
  US 20070150467A1
• Time in Patent Office: 1,715 Days
• Field of Search: 707/728
• US Class Current: 707/728
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

Disclosed is an evaluation technique for text search with black-box scoring functions, where it is unnecessary for the evaluation engine to maintain details of the scoring function. Included is a description of a system for dealing with blackbox searching, proofs of correctness, as well experimental evidence showing that the performance of the technique is comparable in efficiency to those techniques used in custom-built engines.

Claims

1. A computer program product embodied on a computer readable medium, the computer program product comprising computer instructions that implement the following operations:

performing the following in response to a query comprising at least two terms, the query having a first portion comprising at least one term of the at least two terms and a second portion comprising at least one other term of the at least two terms;

selecting a document from a plurality of documents;

determining a score range of possible scores for the selected document by using a scoring function,

where the score range comprises a lower bound and an upper bound, where the upper bounds and lower bounds are not equal,

the determining the score range causing the scoring function to perform a partial evaluation, using only the first portion of the query, for the selected document in order to determine the score range,

a score of the selected document residing within the score range and determinable using the first and second portion from the query; and

determining, based at least on the score range, whether the selected document is relevant to the query, and if the selected document is relevant to the query, retaining the selected document as being relevant to the query,

where the selected document is determined as relevant to the query in response to determining that the lower bound of the score range exceeds a threshold and

the selected document is determined as not relevant to the query in response to determining that the upper bound of the score range does not exceeds the threshold.

2. The computer program product of claim 1, wherein determining whether the selected document is relevant to the query further comprises performing, based at least on the score range and the threshold, one of the following:

choosing the selected document as relevant to the query;

selecting another document;

or

refining the score range for the selected document.

3. The computer program product of claim 2, wherein determining the score range further comprises sending a second query to the scoring function, the second query comprising a number of first terms equivalent to a number of second terms in the at least two terms of the query, each first term in the second query corresponding to a second term in the first query, wherein determining the score range also further comprises setting at least one of the first terms in the second query to one of a wildcard value or a null value, and wherein refining further comprises refining the score range by setting one or more of the first terms previously set to the one of the wildcard value or the null value to corresponding second terms.

4. The computer program product of claim 2, wherein the threshold is set as a smallest score in a heap having a predetermined number of entries, wherein choosing further comprises placing each selected document chosen as relevant to the query into an entry of the heap, wherein a chosen document replaces a previously placed document if the previously placed document has a score that is smaller than a score for the chosen document.

5. The computer program product of claim 2, wherein the threshold is provided.

6. The computer program product of claim 2, wherein each of the plurality of documents correspond to a document identification, wherein the document identifications are placed in an order, and wherein selecting the other document comprising selected the other document by choosing a document identification in the order such that an upper bound of the score range for the other document exceeds the threshold.

7. The computer program product of claim 2, wherein each of the plurality of documents correspond to a document identification, wherein the document identifications are placed in an order, wherein there are a plurality of iterators, each iterator associated with a single term in the at least two terms of the query, wherein each iterator is able to move through the order of document identifications corresponding to the term associated with the iterator, and wherein refining the score range uses at least one of the iterators.

8. The computer program product of claim 7, wherein each iterator is parameterized by one of a wildcard value, the term corresponding to the iterator, or a null value, and wherein iterators set to a document identification within a first range of document identifications are parameterized by the wildcard value, iterators set to a document identification equal to the document identification for the selected document are parameterized by terms corresponding to the iterators, and iterators set to a document identification within a second range of document identifications are parameterized by the null value.

9. The computer program product of claim 8, wherein refining the score range further comprises sending a second query to the second function in order to receive a second score range for the selected document, the second query defined by at least the parameterization of the iterators.

10. The computer program product of claim 9, wherein refining further comprising selecting one of the iterators, wherein the selected iterator is initially set to a document identification in the first range of document identifications, and wherein refining further comprises moving the selected iterator to the document identification of the selected document.

11. The computer program product of claim 9, wherein refining the score range further comprises moving a randomly selected iterator from a document identification in the first range of document identifications to the document identification of the selected document.

12. The computer program product of claim 9, wherein refining the score range further comprises moving the input iterators in a round robin fashion, each of the iterators moved from a document identification in the first range of document identifications to the document identification of the selected document.

13. The computer program product of claim 9, wherein refining the score range further comprises moving a selected iterator of the plurality of iterators that is the least expensive according to a metric to move of the plurality of iterators, wherein the movement occurs from a document identification in the first range of document identifications to the document identification of the selected document.

14. The computer program product of claim 1, wherein determining whether the selected document is relevant to the query further comprises performing, based at least on the score range and the threshold, one of the following:

selecting another document; and

refining the score range for the selected document,

wherein in response to selecting another document, determining the score range and determining whether the selected other document is relevant to the query are performed using the selected other document, and in response to refining the score range for the selected other document, determining whether the selected other document is relevant to the query is performed using the selected document and the refined score range.

15. The computer program product of claim 1, wherein determining the score range further comprises sending a second query to the scoring function, the second query comprising a number of first terms equivalent to a number of second terms in the at least two terms of the query, each first term in the second query corresponding to a second term in the first query, wherein determining the score range also further comprises setting at least one of the second terms in the second query to one of a wildcard value or a null value.

16. The computer program product of claim 1, wherein each of the plurality of documents correspond to a document identification, wherein the document identifications are placed in an order, wherein an index is formed using the document identifications and associated terms, each entry in the index is unique and corresponds to a document identification and at least two terms in a document corresponding to the document identification.

17. The computer program product of claim 1, wherein the scoring function comprises a Boolean function.

18. The computer program product of claim 1, wherein the scoring function comprises at least one of a Term Frequency Inverted Document Frequency (TFIDF) function, a Static Rank function, a Searching by Numbers function, a Lexical Affinities (LA) function a Salience Levels (SL) function, and a threshold predicate function.

19. The computer program product of claim 1, wherein a predetermined score is associated with each document and the scoring function uses the predetermined score in order to determine the score range.

20. A system comprising a processor configured to perform operations of:

in response to a query comprising at least two terms, selecting a document from a plurality of documents, the query having a first portion comprising at least one term of the at least two terms and a second portion comprising at least one other term of the at least two terms;

determining a score range of possible scores for the selected document by using a scoring function,

where the score range comprises a lower bound and an upper bound, where the upper bounds and lower bounds are not equal,

the determining the score range causing the scoring function to perform a partial evaluation, using only the first portion of the query, for the selected document in order to determine the score range,

a score of the selected document residing within the score range and the score determinable using the first and second portion from the query, and

determining, based at least on the score range, whether the selected document is relevant to the query, and if the selected document is relevant to the query, retaining the selected document as being relevant to the query,

where the selected document is determined as relevant to the query in response to determining that the lower bound of the score range exceeds a threshold and

the selected document is determined as not relevant to the query in response to determining that the upper bound of the score range does not exceeds the threshold.

21. The system of claim 20, wherein determining whether the selected document is relevant to the query further comprises performing, based at least on the score range and the threshold, one of the following:

choosing the selected document as relevant to the query;

selecting another document;

or refining the score range for the selected document.

22. The system of claim 20, wherein determining whether the selected document is relevant to the query further comprises performing, based at least on the score range and the threshold, one of the following:

selecting another document; and

refining the score range for the selected document,

wherein in response to selecting another document, determining the score range and determining whether the selected document is relevant to the query are performed using the selected other document, and in response to refining the score range for the selected document, determining whether the selected document is relevant to the query is performed using the selected document and the refined score range.

23. A method comprising:

performing the following in response to a query comprising at least two terms, the query having a first portion comprising at least one term of the at least two terms and a second portion comprising at least one other term of the at least two terms;

selecting a document from a plurality of documents;

determining a score range of possible scores for the selected document by using a scoring function,

where the score range comprises a lower bound and an upper bound, where the upper bounds and lower bounds are not equal,

the determining the score range causing the scoring function to perform a partial evaluation, using only the first portion of the query, for the selected document in order to determine the score range,

a score of the selected document residing within the score range and the score determinable using the first and second portion from the query; and

determining, based at least on the score range, whether the selected document is relevant to the query, and if the selected document is relevant to the query, retaining the selected document as being relevant to the query,

where the selected document is determined as relevant to the query in response to determining that the lower bound of the score range exceeds a threshold and

the selected document is determined as not relevant to the query in response to determining that the upper bound of the score range does not exceeds the threshold.

24. The method of claim 23, wherein determining whether the selected document is relevant to the query further comprises performing, based at least on the score range and the threshold, one of the following:

choosing the selected document as relevant to the query;

selecting another document;

or refining the score range for the selected document.

25. The method of claim 24, wherein in response to selecting another document, determining the score range and determining whether the selected document is relevant to the query are performed using the selected other document, and in response to refining the score range for the selected document, determining whether the selected document is relevant to the query is performed using the selected document and the refined score range.