Patent ID: 7925651

Claim:
A computer implemented method of training a ranking component to rank items using a computer with a processor, comprising: generating, with the processor, a dependency structure having at least one parent node and at least two dependent nodes, dependent from the parent node, the dependency structure ranking items that pass through nodes in the dependency structure when the items are applied to the dependency structure with the processor, each parent node including decision criteria for deciding which dependent node to send an item to, as the item passes past the parent node, the rank of an item relative to other items being dependent on a position of a leaf node to which the item passes relative to a position of other leaf nodes to which the other items pass, each of the leaf nodes in the dependency structure representing a rank that is different from all other leaf nodes in the dependency structure, the rank indicating how closely each item corresponds to a user input relative to other items in a set of items; and training the dependency structure with the processor by iteratively performing operations to define the decision criteria at the nodes, the operations comprising at least one of data splitting and data merging on items of training data as the items of training data pass through the nodes, each of the operations being performed such that a ranking function that is indicative of a quality of a rank of the items of training data is optimized for each node, the optimization at each node including assuming a worst possible ranking for the items of training data sent through the node, calculating a minimum normalized discounted cumulative gain function based on the worst possible ranking, and finding a split that gives a maximum value of the minimum normalized discounted cumulative gain function.