Method and system for query performance prediction

Patent metadata

Field	Value
Publication number	US-2019171742-A1
Application number	US-201715832810-A
Country	US
Kind code	A1
Filing date	Dec 6, 2017
Priority date	Dec 6, 2017
Publication date	Jun 6, 2019
Grant date	—

Abstract

A computer-implemented method, computerized apparatus and computer program product for query performance prediction, the method comprising: obtaining a result list comprising a listing of documents retrieved from a collection in response to a query; obtaining for each of the listed documents in the result list a score indicating a measure of the document's relevance to the query; sampling the result list to obtain a plurality of sub-lists each of which comprising a listing of documents subsumed by the result list; for each of the plurality of sub-lists, analyzing scores of the documents listed therein to obtain a sample performance estimator; and estimating performance of the result list based on the sample performance estimator of each of the plurality of sub-lists.

First claim

What is claimed is:

1 . A computer-implemented method comprising:
obtaining a result list comprising a listing of documents retrieved from a collection in response to a query; obtaining for each of the listed documents in the result list a score indicating a measure of the document's relevance to the query; sampling the result list to obtain a plurality of sub-lists each of which comprising a listing of documents subsumed by the result list; for each of the plurality of sub-lists, analyzing scores of the documents listed therein to obtain a sample performance estimator; and estimating performance of the result list based on the sample performance estimator of each of the plurality of sub-lists.

2 . The computer-implemented method of claim 1 , wherein said sampling of the result list is without replacement, such that a listed document is selected to a sub-list at most once.

3 . The computer-implemented method of claim 1 , wherein said sampling of the result list is performed using a ranked-biased random variable distribution.

4 . The computer-implemented method of claim 1 , wherein said sampling of the result list is performed using a round-robin scheme in accordance with a rank-ordering of the listed documents.

5 . The computer-implemented method of claim 1 , wherein the sample performance estimator is a variance-like measure of the listed documents' scores.

6 . The computer-implemented method of claim 1 , further comprising:
determining for each of the plurality of sub-lists a weight in accordance with a predetermined weighting scheme; wherein said estimating performance of the result list is further based on the weight determined for each of the plurality of sub-lists.

7 . The computer-implemented method of claim 6 , wherein the predetermined weighting scheme is selected from the group consisting of: a uniform weighting; a weighting based on a degree of similarity between a sub-list and the result list; and, a weighting based on a measure of deviation of a sub-list documents' scores from a score of the collection.

8 . The computer-implemented method of claim 1 , wherein said estimating further comprises applying normalization to mitigate a dependency of the sample performance estimator in the query.

9 . The computer-implemented method of claim 8 , wherein normalization is applied using a perplexity measure modeling an extent to which the query represents an underlying information need.

10 . The computer-implemented method of claim 8 , wherein normalization is applied using the collection as an ineffective reference document.

11 . A computerized apparatus having a processor, the processor being adapted to perform the steps of:
obtaining a result list comprising a listing of documents retrieved from a collection in response to a query; obtaining for each of the listed documents in the result list a score indicating a measure of the document's relevance to the query; sampling the result list to obtain a plurality of sub-lists each of which comprising a listing of documents subsumed by the result list; for each of the plurality of sub-lists, analyzing scores of the documents listed therein to obtain a sample performance estimator; and estimating performance of the result list based on the sample performance estimator of each of the plurality of sub-lists.

12 . The computerized apparatus of claim 11 , wherein said sampling of the result list is without replacement, such that a listed document is selected to a sub-list at most once.

13 . The computerized apparatus of claim 11 , wherein said sampling of the result list is performed using a ranked-biased random variable distribution.

14 . The computer-implemented method of claim 1 , wherein said sampling of the result list is performed using a round-robin scheme in accordance with a rank-ordering of the listed documents.

15 . The computerized apparatus of claim 11 , wherein the sample performance estimator is a variance-like measure of the listed documents' scores.

16 . The computerized apparatus of claim 11 , wherein the processor being further adapted to perform the steps of:
determining for each of the plurality of sub-lists a weight in accordance with a predetermined weighting scheme; wherein said estimating performance of the result list is further based on the weight determined for each of the plurality of sub-lists.

17 . The computerized apparatus of claim 16 , wherein the predetermined weighting scheme is selected from the group consisting of: a uniform weighting; a weighting based on a degree of similarity between a sub-list and the result list; and, a weighting based on a measure of deviation of a sub-list documents' scores from a score of the collection.

18 . The computerized apparatus of claim 11 , wherein said estimating further comprises applying normalization to mitigate a dependency of the sample performance estimator in the query.

19 . The computerized apparatus of claim 18 , wherein normalization is applied using a perplexity measure modeling an extent to which the query represents an underlying information need.

20 . A computer program product comprising a non-transitory computer readable storage medium retaining program instructions, which program instructions when read by a processor, cause the processor to perform a method comprising:
obtaining a result list comprising a listing of documents retrieved from a collection in response to a query; obtaining for each of the listed documents in the result list a score indicating a measure of the document's relevance to the query; sampling the result list to obtain a plurality of sub-lists each of which comprising a listing of documents subsumed by the result list; for each of the plurality of sub-lists, analyzing scores of the documents listed therein to obtain a sample performance estimator; and estimating performance of the result list based on the sample performance estimator of each of the plurality of sub-lists.

Assignees

• IBM

Inventors

• Cohen Doron
• Erera Shai
• Roitman Haggai
• Weiner Bar

Classifications

• G06F17/30483 Primary

  Physics · mapped topic

• G06F17/30011

  Physics · mapped topic

• G06F17/3053

  Physics · mapped topic

• G06F16/2453 Primary

  Query optimisation · CPC title

• G06F16/24553 Primary

  of query operations · CPC title