Adaptive Evaluation of Text Search Queries With Blackbox Scoring Functions

• US 20070150467A1
• Filed: 11/21/2006
• Published: 06/28/2007
• Est. Priority Date: 05/30/2003
• Status: Active Grant

• Current Assignee: Eugene Shekita, Kevin Beyer, Robert Lyle, Sridhar Rajagopalan
• Original Assignee: Eugene Shekita, Kevin Beyer, Robert Lyle, Sridhar Rajagopalan
• Inventors: Rajagopalan, Sridhar, Lyle, Robert, Shekita, Eugene, Beyer, Kevin
• Granted Patent: US 7,991,771 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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-19. -19. (canceled)

20. 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 including at least one term;

selecting a document from a plurality of documents;

determining a score range for the selected document by using a scoring function, the determining the score range causing the scoring function to perform a partial evaluation, using a portion of the at least one term from the query, of a score for the selected document in order to determine the score range, the score of the selected document residing within the score range and determinable using all of the at least one term 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.

21. The computer program product 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 a 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 computer program product of claim 21, 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. The computer program product of claim 21, wherein determining the score range further comprises sending a second query to the scoring function, the second query including a number of first terms equivalent to a number of second terms in the at least one term 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.

24. The computer program product of claim 20, wherein determining the score range further comprises sending a second query to the scoring function, the second query including a number of first terms equivalent to a number of second terms in the at least one term 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.

25. The computer program product of claim 21, wherein the threshold is set as a smallest score in a list 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 list, 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.

26. The computer program product of claim 21, wherein the threshold is provided.

27. The computer program product of claim 21, 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.

28. The computer program product of claim 20, 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 one term in a document corresponding to the document identification.

29. The computer program product of claim 20, wherein the scoring function comprises a Boolean function.

30. The computer program product of claim 20, 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.

31. The computer program product of claim 21, 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 one term 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.

32. The computer program product of claim 31, 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.

33. The computer program product of claim 32, 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.

34. The computer program product of claim 33, 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.

35. The computer program product of claim 33, 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.

36. The computer program product of claim 33, 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.

37. The computer program product of claim 33, 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.

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

39. A system comprising a processor configured to perform operations of, in response to a query including at least one term, selecting a document from a plurality of documents, determining a score range for the selected document by using a scoring function, the determining the score range causing the scoring function to perform a partial evaluation, using a portion of the at least one term from the query, of a score for the selected document in order to determine the score range, the score of the selected document residing within the score range and determinable using all of the at least one term from the query, the operations further including 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.

40. The system of claim 39, wherein determining whether the selected document is relevant to the query further comprises performing, based at least on the score range and a 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.

41. The system of claim 40, 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.

42. A method comprising:

performing the following in response to a query including at least one term;

selecting a document from a plurality of documents;

determining a score range for the selected document by using a scoring function, the determining the score range causing the scoring function to perform a partial evaluation, using a portion of the at least one term from the query, of a score for the selected document in order to determine the score range, the score of the selected document residing within the score range and determinable using all of the at least one term 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.

43. The method of claim 42, wherein determining whether the selected document is relevant to the query further comprises performing, based at least on the score range and a 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.

44. The method of claim 43, 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.