Efficient Data Layout Techniques for Fast Machine Learning-Based Document Ranking

• US 20100070457A1
• Filed: 09/16/2008
• Published: 03/18/2010
• Est. Priority Date: 09/16/2008
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Panigrahi, Sapan, Kejariwal, Arun, Vaitheeswaran, Girish
• Granted Patent: US 8,533,129 B2
• Time in Patent Office: Days
• US Class Current: 706/59
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A computer readable medium stores a program for optimization for a search, and has sets of instructions for receiving a first decision tree. The first decision tree includes several nodes, and each node is for comparing a feature value to a threshold value. The instructions are for weighting the nodes within the first decision tree, determining the weighted frequency of a first feature within the first decision tree, and determining the weighted frequency of a second feature within the first decision tree. The instructions order the features based on the determined weighted frequencies, and store the ordering such that values of features having higher weighted frequencies are retrieved more often than values of features having lower weighted frequencies within the first decision tree.

Claims

1. A method of optimization for a search, the method comprising:

receiving a first decision tree comprising a plurality of nodes, each node for comparing a feature value to a threshold value;

determining the frequency of a first feature within the first decision tree;

determining the frequency of a second feature within the first decision tree;

ordering the features based on the determined frequencies;

storing the ordering such that values of features having higher frequencies are retrieved more often than values of features having lower frequencies within the first decision tree.

2. The method of claim 1, the first decision tree derived from a machine learning-based ranking algorithm.

3. The method of claim 1, further comprising a set of decision trees including the first decision tree, the method further comprising determining the frequency of the first feature in the set of decision trees.

4. The method of claim 1, the determined frequencies comprising static frequencies at compile time, the ordering performed at compile time.

5. The method of claim 1, the storing comprising grouping the higher frequency into memory blocks that are closely packed such that higher frequency feature values are loaded more often into cache from memory.

6. The method of claim 1, further comprising compiling the nodes of the first decision tree into a run time algorithm such that the higher frequency feature values are retrieved at run time by prefetching.

7. The method of claim 1, the first decision tree comprising a root node, a plurality of internal nodes, and at least one leaf node.

8. The method of claim 1, wherein the features within the first decision tree are representative of the features of a web page document available for searching online, wherein the feature values are used to rank the web page document based on a calculated relevance to a search query.

9. A method of optimization for a search, the method comprising:

receiving a first decision tree comprising a plurality of nodes, each node for comparing a feature value to a threshold value;

weighting the nodes within the first decision tree;

determining the weighted frequency of a first feature within the first decision tree;

determining the weighted frequency of a second feature within the first decision tree;

ordering the features based on the determined weighted frequencies;

storing the ordering such that values of features having higher weighted frequencies are retrieved more often than values of features having lower weighted frequencies within the first decision tree.

10. The method of claim 9, the first decision tree derived from a machine learning-based ranking algorithm.

11. The method of claim 9, further comprising a set of decision trees including the first decision tree, the method further comprising:

weighting the nodes for each decision tree; and

determining the weighted frequency of the first feature in the set of decision trees.

12. The method of claim 9, the determined frequencies comprising static frequencies at compile time, the ordering performed at compile time.

13. The method of claim 9, the storing comprising grouping values for higher frequency features into memory blocks that are closely packed such that higher frequency feature values are loaded more often into cache from memory.

14. The method of claim 9, further comprising compiling the nodes of the first decision tree into a run time algorithm such that the higher frequency feature values are retrieved at run time by prefetching.

15. The method of claim 9, the first decision tree comprising a root node, a plurality of internal nodes, and at least one leaf node, wherein the root node and each internal node comprises a binary decision node, wherein the decision comprises a Boolean expression of whether a particular feature value F. is less than a threshold value for the node, wherein if the Boolean expression is true then the tree is traversed in the direction of one of two next nodes within the first decision tree.

16. The method of claim 9, wherein the features within the first decision tree are representative of the features of a web page document available for searching online, wherein the feature values are used to rank the web page document based on a calculated relevance to a search query.

17. The method of claim 9, further comprising weighting higher the nodes closer to a root node.

18. The method of claim 9, the first decision tree comprising one root node, fifteen internal nodes, and sixteen leaf nodes organized into layers having node weights, wherein the root node comprises the highest weight layer and one or more leaf nodes comprise the lowest weight layer.

19. A computer readable medium storing a program for optimization for a search, the computer readable medium having sets of instructions for:

receiving a first decision tree comprising a plurality of nodes, each node for comparing a feature value to a threshold value;

determining the frequency of a first feature within the first decision tree;

determining the frequency of a second feature within the first decision tree;

ordering the features based on the determined frequencies; and

storing the ordering such that values of features having higher frequencies are retrieved more often than values of features having lower frequencies within the first decision tree.

20. A computer readable medium storing a program for optimization for a search, the computer readable medium having sets of instructions for:

receiving a first decision tree comprising a plurality of nodes, each node for comparing a feature value to a threshold value;

weighting the nodes within the first decision tree;

determining the weighted frequency of a first feature within the first decision tree;

determining the weighted frequency of a second feature within the first decision tree;

ordering the features based on the determined weighted frequencies; and

storing the ordering such that values of features having higher weighted frequencies are retrieved more often than values of features having lower weighted frequencies within the first decision tree.