Federation for parallel searching
View Patent ↗A search engine can be configured to improve search times by implementing a parallel computing architecture. The index is split across a plurality of independent search nodes. A query is communicated to each of the parallel nodes and the query is searched in each independent node. The results from each node are routed to a federator that is configured to aggregate the results to a result set. The federator is configured to determine a subset of intermediate results to retrieve and aggregate from each of the independent nodes. The federator determines a number of results to retrieve from each of the nodes based at least in part on the number of nodes and the number of search results desired in the results set.
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 the query from a user;
distributing the query to a plurality of independent computational nodes, each computational node configured to search a corresponding segment of an index of the corpus of documents;
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;
determining a number of results n 1 to retrieve from each of the intermediate results lists obtained by the computational nodes, the determined number of results n 1 providing a quantitative probability of not retrieving one most responsive result in an aggregated number of results, where the determined number of results is less than the aggregated number of results and the quantitative probability is given by a statistical formula:
(
s
-
1
n
1
)
/
n
n
1
,
wherein n is a number of independent computational nodes and s is the number of aggregated results; and
aggregating the determined number of results from each of the intermediate results lists containing the determined number of results or more into an output result list, otherwise aggregating all results from each of the intermediate results lists containing fewer than the determined number of results into the output result list.
2. The method of claim 1 , wherein the corpus of documents is evenly distributed among the independent computational nodes.
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 based in part on a number of independent computational nodes.
6. The method of claim 5 , wherein the determined number of results is further based on the aggregated number of results in the output result list.
7. The method of claim 1 , wherein determining the number of results comprises determining the number of results independent of a number of results in each intermediate results lists.
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 nodes.
10. The method of claim 1 , wherein aggregating the number of results into the output result list comprises:
retrieving up to the determined number of results from each of the intermediate results lists to generate the output result list;
and ranking the documents in the output result list.
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 method of processing the query comprising:
obtaining the query from a user;
distributing the query to a plurality of independent computational nodes, each computational node configured to search a corresponding segment of an index of the corpus of documents;
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;
determining a number of results n 1 to retrieve from each intermediate results list based on a total number of results desired, a number of independent nodes, and a quantitative probability of not retrieving one most responsive result in the total number of results desired, where the determined number of results n 1 is less than the total number of results desired and the quantitative probability is given by a statistical formula:
(
s
-
1
n
1
)
/
n
n
1
,
wherein n is a number of independent computational nodes and s is the total number of results desired;
retrieving up to the determined number of results from each of the intermediate results lists; and
generating an aggregate output result list having no more than the total number of results desired.
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, an apparatus for processing the query comprising:
a plurality 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; 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 one intermediate result list to generate an output result list, the output result list including an aggregated number of results, the federator selecting the portion of the at least one intermediate result list based in part on a quantitative probability of not retrieving one most responsive result in the aggregated number of results, wherein the federator is configured to determine a number of results n 1 to retrieve from each of the intermediate results lists based at least in part on a number of computational nodes n with the quantitative probability being given by a statistical formula:
(
s
-
1
n
1
)
/
n
n
1
,
wherein s is the number of aggregated results.
13. The apparatus of claim 12 , wherein the corpus of documents is evenly distributed among the corresponding segments of the index.
14. The apparatus 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 apparatus 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 apparatus of claim 12 , wherein the federator is configured to determine the number of results to retrieve from each of the intermediate results lists based at least in part on the aggregated number of results in the output result list.
17. The apparatus 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.
18. The apparatus of claim 17 , wherein the formatter is configured to retrieve at least a portion of documents identified in the output results list.