PRODUCTIVE DISTRIBUTION FOR RESULT OPTIMIZATION WITHIN A HIERARCHICAL ARCHITECTURE

• US 20100318516A1
• Filed: 10/30/2009
• Published: 12/16/2010
• Est. Priority Date: 06/10/2009
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Przebinda, Viktor, Nicolaou, Cos, Neveitt, William, Nowicki, Kacper, Kolen, John, Eiron, Nadav
• Application Number:
  US12/609,788
• Publication Number:
  US 20100318516A1
• Time in Patent Office: Days
• US Class Current: 707/736
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

A producer node may be included in a hierarchical, tree-shaped processing architecture, the architecture including at least one distributor node configured to distribute queries within the architecture, including distribution to the producer node and at least one other producer node within a predefined subset of producer nodes. The distributor node may be further configured to receive results from the producer node and results from the at least one other producer node and to output compiled results therefrom. The producer node may include a query pre-processor configured to process a query received from the distributor node to obtain a query representation using query features compatible with searching a producer index associated with the producer node to thereby obtain the results from the producer node, and a query classifier configured to input the query representation and output a prediction, based thereon, as to whether processing of the query by the at least one other producer node within the predefined subset of producer nodes will cause results of the at least one other producer node to be included within the compiled results.

Claims

1. A computer system including instructions stored on a computer-readable medium, the computer system comprising:

a producer node of a hierarchical, tree-shaped processing architecture, the architecture including at least one distributor node configured to distribute queries within the architecture, including distribution to the producer node and at least one other producer node within a predefined subset of producer nodes, the distributor node being further configured to receive results from the producer node and results from the at least one other producer node and to output compiled results therefrom, the producer node including

a query pre-processor configured to process a query received from the distributor node to obtain a query representation using query features compatible with searching a producer index associated with the producer node to thereby obtain the results from the producer node; and

a query classifier configured to input the query representation and output a prediction, based thereon, as to whether processing of the query by the at least one other producer node within the predefined subset of producer nodes will cause results of the at least one other producer node to be included within the compiled results.

2. The system of claim 1 wherein the query classifier is configured to provide the prediction to the distributor node in conjunction with obtaining the query representation and before producing the results from the producer node, so that the producer node and the at least one other producer node provide their respective results to the distributor node in parallel.

3. The system of claim 1 wherein the query classifier is configured to determine the at least one other producer node from a plurality of other producer nodes within the architecture and to identify the at least one other producer node as a target node to which the query should be forwarded.

4. The system of claim 1 wherein the query classifier is configured to input at least two query features associated with the query representation and to compute the prediction based thereon.

5. The system of claim 4 wherein the query classifier is configured to select the at least two query features from a set of query features associated with the query representation.

6. The system of claim 4 wherein at least one of the at least two query features includes a term count of the terms within the query.

7. The system of claim 1 wherein the query classifier is configured to provide the prediction including a value within a range representing an extent to which the at least one other producer node is likely to be included within the compiled results.

8. The system of claim 1 wherein the query classifier is configured to provide the prediction including a value within a range representing an extent to which the at least one other producer should process the query for use in providing the results from the at least one other producer node.

9. The system of claim 1 wherein the producer node comprises a classification manager configured to input classification data including query features associated with the query representation, results from the at least one other producer node, and one of a plurality of machine learning algorithms, and configured to construct, based thereon, a classification model for output to the query classifier for use in outputting the prediction.

10. The system of claim 9 wherein the classification manager is configured to track the results from the at least one other node and to update the classification data and the classification model therewith.

11. The system of claim 9 wherein the producer node comprises a monitor configured to trigger the distributor node to periodically send a subset of the queries to the at least one other producer node whether indicated by the query classifier or not, and to update the classification data based thereon.

12. The system of claim 1 wherein the results from the producer node are obtained from a data source associated with the producer node using the producer index, and the results form the at least one other producer node are obtained form a data source associated with the at least one other producer node using a corresponding index, and wherein the at least one other producer node is less cost-effective to access when compared to the producer node.

13. A computer-implemented method in which at least one processor implements at least the following operations, the method comprising:

receiving a query at a producer node from at least one distributor node within a hierarchical, tree-shaped processing architecture, the architecture including the at least one distributor node configured to distribute queries within the architecture, including distribution to the producer node and at least one other producer node, the distributor node being further configured to receive results from the producer node and results from the at least one other producer node and to output compiled results therefrom;

pre-processing the query received from the distributor node to obtain a query representation using query features compatible with searching a producer index associated with the producer node to thereby obtain the results from the producer node; and

classifying the query using the query representation to thereby output a prediction, based thereon, as to whether processing of the query by the at least one other producer node will cause results of the at least one other producer node to be included within the compiled results.

14. The method of claim 13 wherein the classifying the query comprises:

providing the prediction to the distributor node in conjunction with obtaining the query representation and before producing the results from the producer node, so that the producer node and the at least one other producer node provide their respective results to the distributor node in parallel.

15. The method of claim 13 wherein the classifying the query comprises:

inputting classification data including query features associated with the query representation, results from the at least one other producer node, and one of a plurality of machine learning algorithms, and

constructing, based thereon, a classification model for use in outputting the prediction.

16. The method of claim 15 wherein the classifying the query comprises:

triggering the distributor node to periodically send a subset of the queries to the at least one other producer node whether indicated by the prediction or not, and to update the classification data based thereon.

17. A computer program product, the computer program product being tangibly embodied on a computer-readable medium and including executable code that, when executed, is configured to cause a data processing apparatus to:

receive a query at a producer node from at least one distributor node within a hierarchical, tree-shaped processing architecture, the architecture including the at least one distributor node configured to distribute queries within the architecture, including distribution to the producer node and at least one other producer node, the distributor node being further configured to receive results from the producer node and results from the at least one other producer node and to output compiled results therefrom;

pre-process the query received from the distributor node to obtain a query representation using query features compatible with searching a producer index associated with the producer node to thereby obtain the results from the producer node; and

classify the query using the query representation to thereby output a prediction, based thereon, as to whether processing of the query by the at least one other producer node will cause results of the at least one other producer node to be included within the compiled results.

18. The computer program product of claim 17 wherein, in classifying the query, the executed instructions cause the data processing apparatus to:

provide the prediction to the distributor node in conjunction with obtaining the query representation and before producing the results from the producer node, so that the producer node and the at least one other producer node provide their respective results to the distributor node in parallel.

19. The computer program product of claim 17 wherein, in classifying the query, the executed instructions cause the data processing apparatus to:

input classification data including query features associated with the query representation, results from the at least one other producer node, and one of a plurality of machine learning algorithms; and

construct, based thereon, a classification model for use in outputting the prediction.

20. The computer program product of claim 19 wherein, in classifying the query, the executed instructions cause the data processing apparatus to:

trigger the distributor node to periodically send a subset of the queries to the at least one other producer node whether indicated by the prediction or not; and

update the classification data based thereon.