Granted Patent B1

US 8,429,147 · App. 13/091,967 · Granted Apr 23, 2013

Abstract

Claims (70)

1. In a computerized search system in which queries are submitted by users who receive, in response, a list of documents selected from a corpus of documents wherein the list comprises documents deemed responsive to a user's query, a method of processing the query comprising:

obtaining a query from a user;

distributing the query to a number of independent computational nodes, each computational node configured to search a corresponding segment of an index of the corpus of documents, the number of computational nodes being greater than one;

running the query in each of the computational nodes against the corresponding segment of the index of the corpus of documents to obtain from each of the computational nodes an intermediate results list of zero or more documents in the document corpus deemed responsive to the query;

identifying a desired probability of not retrieving one most responsive result in an aggregated number of results in an aggregated list of results;

determining a number of results to retrieve from each of the intermediate results lists obtained from the computational nodes, the number of results being determined to provide a determinable probability of not retrieving one most responsive result in the aggregated number of results in the aggregated list of results, the determinable probability being less than or equal to the desired probability of not retrieving one most responsive result in the aggregated list of results, where the determined number of results is less than the aggregated number of results, the determinable probability being determined based on an estimated distribution of documents among the computational nodes and further based on the number of computational nodes; and

aggregating the determined number of results from each of the intermediate results lists containing the determined number of results or more into the aggregated list of results, otherwise aggregating all results from each of the intermediate results lists containing fewer than the determined number of results into the aggregated list of results.

2. The method of claim 1 , wherein the corpus of documents is evenly distributed among the independent computational nodes and the estimated distribution is an even distribution.

3. The method of claim 1 , wherein each document within the corpus of documents is randomly assigned to one segment of the index.

4. The method of claim 1 , wherein each document within the corpus of documents is pseudo-randomly assigned to one segment of the index.

5. The method of claim 1 , wherein determining the number of results comprises determining the number of results using a statistical formula based in part on the number of independent computational nodes.

6. The method of claim 5 , wherein the statistical formula is further based on the aggregated number of results in the aggregated list of results.

7. The method of claim 6 , wherein the statistical formula represents taking the aggregated number of results, s, in the aggregated list of results minus one, choosing the number of results, n 1 , and dividing by the number of independent computational nodes, n, raised to power n 1 , as follows:

(

s

-

1

n

1

)

/

n

n

1

⁡

(

s

-

1

n

1

)

/

n

n

1

.

8. The method of claim 1 , wherein determining the number of results comprises determining a plurality of numbers of results with one of the plurality of numbers of results applicable to each of the intermediate results lists.

9. The method of claim 1 , wherein the same determined number of results applies for all of the computational nodes.

10. The method of claim 1 , wherein aggregating the determined number of results into the aggregated list of results comprises:

retrieving up to the determined number of results from each of the intermediate results lists to generate the aggregated list of results; and

ranking the documents in the aggregated list of results.

11. In a computerized search system in which queries are submitted by users who receive, in response, a list of documents selected from a corpus of documents wherein the list comprises documents deemed responsive to a user's query, a non-transitory machine-readable storage medium comprising instructions thereon that, when executed by at least one machine, cause the at least one machine to:

obtain a query from a user;

distribute the query to a number of independent computational nodes, each computational node configured to search a corresponding segment of an index of the corpus of documents, the number of computational nodes being greater than one;

run the query in each of the computational nodes against the corresponding segment of the index of the corpus of documents to obtain from each of the computational nodes an intermediate results list of zero or more documents in the document corpus deemed responsive to the query;

identify a desired probability of not retrieving one most responsive result in an aggregated number of results in an aggregated list of results;

determine a number of results to retrieve from each of the intermediate results lists obtained from the computational nodes, the number of results being determined to provide a determinable probability of not retrieving one most responsive result in the aggregated number of results in the aggregated list of results, the determinable probability being less than or equal to the desired probability of not retrieving one most responsive result in the aggregated list of results, where the determined number of results is less than the aggregated number of results, the determinable probability being determined based on an estimated distribution of documents among the computational nodes and further based on the number of computational nodes;

retrieve up to the determined number of results from each of the intermediate results lists; and

generate the aggregated list of results having no more than the number of results.

12. In a computerized search system in which queries are submitted by users who receive, in response, a list of documents selected from a corpus of documents wherein the list comprises documents deemed responsive to a user's query, a system for processing the query comprising:

a number of computational nodes, each computational node configured to search a corresponding segment of an index of the corpus of documents to obtain an intermediate results list of zero or more documents in the document corpus deemed responsive to the query, the number of computational nodes being greater than one; and

a federator configured to receive the query and communicate the query to each of the plurality of computational nodes and configured to aggregate a portion of at least two intermediate result lists to generate an output result list, the output result list including an aggregated number of results, the federator identifying a desired probability of not retrieving one most responsive result in the output result list, and determining the portion so as to provide a determinable probability of not retrieving one most responsive result in the output results list, the determinable probability being less than or equal to the desired probability of not retrieving one most responsive result in the output results list, the determinable probability being determined based on an estimated distribution of documents among the computational nodes and further based on the number of computational nodes, wherein the federator is configured to determine the portion using a statistical formula based in part on the number of computational nodes, wherein the statistical formula is further based on the aggregated number of results, and wherein the statistical formula represents taking the aggregated number of results, s, choosing a number of results n 1 , in the portion and dividing by the number of computational nodes, n, raised to power n 1 , as follows:

(

s

-

1

n

1

)

/

n

n

1

.

13. The system of claim 12 , wherein the corpus of documents is evenly distributed among the corresponding segments of the index and the estimated distribution is an even distribution.

14. The system of claim 12 , wherein each of the corresponding segments of the index of the corpus of documents references documents randomly allocated to the segment of the index.

15. The system of claim 12 , wherein each of the corresponding segments of the index of the corpus of documents references documents pseudo-randomly allocated to the segment of the index.

16. The system of claim 12 , further comprising a formatter coupled to the federator and configured to generate a response to the query based on the output result list.

17. The system of claim 16 , wherein the formatter is configured to retrieve at least a portion of documents identified in the output results list.

Assignments (16)