Adaptive evaluation of text search queries with blackbox scoring functions

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.

What is claimed is:  
     
         1 . A computer program product embodied on a computer readable medium, the computer program product comprising computer instructions that implement a search algorithm comprising a function having an input for receiving, while there is at least one candidate location in an order of locations, a score range for the candidate location, the algorithm comparing the score range to a threshold within a range of possible scores, wherein if a lower bound of the score range for the candidate location exceeds the threshold then the candidate location is retained as a result and a next location is selected, and wherein if an upper bound of the score range is at or below the threshold the candidate location is discarded and the next location is selected, and wherein if the score of the candidate location is indeterminate, then the score range for the candidate location is refined.  
     
     
         2 . The computer program product as in  claim 1 , wherein the next location is selected by choosing the next location greater than the candidate location such that the upper bound exceeds the threshold.  
     
     
         3 . The computer program product as in  claim 1 , wherein the algorithm receives the score range from a blackbox scoring function.  
     
     
         4 . The computer program product as in  claim 3 , wherein the blackbox scoring function comprises a Boolean function.  
     
     
         5 . The computer program product as in  claim 4 , wherein the function comprises instructions for selecting the next location by choosing the next location greater than the candidate location such that the upper bound exceeds the threshold.  
     
     
         6 . The computer program product as in  claim 3 , wherein the blackbox 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.  
     
     
         7 . The computer program product as in  claim 3 , wherein the blackbox scoring function provides an under-estimate of the score range.  
     
     
         8 . The computer program product as in  claim 1 , wherein the score range for the candidate location is refined by advancing an input iterator that is set before the candidate location to the candidate location and reevaluating the score range.  
     
     
         9 . The computer program product as in  claim 8 , wherein advancing the input iterator comprises advancing a randomly selected input iterator.  
     
     
         10 . The computer program product as in  claim 8 , wherein advancing the input iterator comprises advancing the input iterator in a round robin fashion.  
     
     
         11 . The computer program as in  claim 8 , wherein advancing the input iterator comprises advancing the input iterator that is the least expensive to advance.  
     
     
         12 . The computer program product as in  claim 8 , wherein advancing the input iterator comprises advancing the sparsest input iterator.  
     
     
         13 . The computer program product as in  claim 12 , wherein advancing the sparsest input iterator comprises measuring the effectiveness of the input iterator to advance the candidate location.  
     
     
         14 . The computer program product as in  claim 13 , wherein measuring the effectiveness comprises dividing total progress attributed to the input iterator by a number of toss operations for the input iterator.  
     
     
         15 . The computer program product as in  claim 8 , wherein advancing the input iterator comprises selecting a first iterator in an order of iterators set before the candidate location such that when all iterators after the chosen iterator are assumed to occur at the candidate location, and all iterators set before the chosen iterator are assumed to not occur at the candidate location, and the upper bound is above the threshold when the chosen iterator is assumed to occur at the candidate location, and the upper bound is below the threshold when the chosen iterator is assumed to not occur at the candidate location.  
     
     
         16 . The computer program product as in  claim 8 , wherein advancing the input iterator comprises selecting a combination of techniques.  
     
     
         17 . The computer program product as in  claim 1 , wherein the candidate location comprises a predetermined score for the score range.  
     
     
         18 . A system for implementing a search algorithm, comprising: 
 a processor for operating an algorithm that comprises an input for receiving from a blackbox scoring function a score for at least one candidate location in an order of locations, wherein the algorithm compares the score to a threshold, and if the score exceeds the threshold then the candidate location is stored as a result and a next location is selected, and if the score is at or below the threshold the candidate location is discarded and the next location is selected, and wherein if the score of the candidate location is indeterminate, then the score for the candidate location is refined; wherein each result is stored in a table of results ordered by relevance.    
     
     
         19 . A method for implementing a search of locations in a body of data for relevant terms, the method comprising: 
 providing an index of locations comprised of terms, wherein a score for the relevant terms in a candidate location is provided by a scoring function and associated with the candidate location; and,    while there are candidate locations:    refining the score range if the score of the candidate location is indeterminate, otherwise, storing each candidate location as a result if a lower bound of the score range for the candidate location exceeds a threshold within a range of possible scores, discarding the candidate location if the score range is at or below an upper bound for the score range and selecting a next location.