# US 2019/0171742 A1 · Method and system for query performance prediction

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0171742 A1
- Document ID: US20190171742A1
- Status: Published application
- Kind: A1
- Application number: 15/832,810
- Filed: 2017-12-06
- Published: 2019-06-06
- Earliest claimed: 2017-12-06
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Doron Cohen; Shai Erera; Haggai Roitman; Bar Weiner
- Web page: https://patentgrep.com/patent/US20190171742A1

## CPC

- G06F 16/24553: {of query operations}
- G06F 16/2453: Query optimisation
- G06F 16/24578: {using ranking}
- G06F 16/93: Document management systems
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 6)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 8)

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

### Claim 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.

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 11)

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

### Claim 14 (depends on 1)

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.

### Claim 15 (depends on 11)

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

### Claim 16 (depends on 11)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 11)

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.

### Claim 19 (depends on 18)

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.

### Claim 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.
