Method to rank documents by a computer, using additive ensembles of regression trees and cache optimisation, and search engine using such a method

A method of managing a cache memory configured to use a branch prediction mechanism to rank stored documents, in particular text or image or audio or video documents, using a ranking model represented by an ensemble of additive regression trees Th with h=1, . . . H, H being a positive integer, the method providing a score value for each document in a set of M candidate documents di with i=1, . . . , M according to their relevance to a given user query q, wherein ranking the documents according to the branch prediction mechanism comprises:

• each query-document pair (q, di) is represented by a vector x whose component x[j] with j=1, . . . , P, with P positive integer, is a numerical feature values representing a corresponding feature of the set ={f0, f1, . . . fP} of features characterizing the query-document pair (q, di);
• each tree Th=(Nh, Lh) comprises a set of nodes Nh={n0, n1, . . . }, wherein each node is associated with a Boolean test over a specific feature fϕ∈ and a pre-determined feature threshold γ in the form of x[φ]≤γ, and a set of leaves Lh={l0, l1, . . . }, each leaf being associated to a prediction value representing the possible contribution of tree Th to the score value of a document, each node being the starting point of a right subtree and a left subtree connecting to respective node or leaf;
• the nodes of said set of nodes whose Boolean conditions evaluate to FALSE are termed “false nodes,” and “true nodes” otherwise;
• the method providing, for a document, execution of a step of traversing all the trees Th in the ensemble , by taking the right subtree if a visited node is a false node, and the left subtree otherwise, until a leaf is reached, which is termed “exit leaf” eh(x)∈Lh with associated prediction value eh(x).val, the score value s(x) of the document being finally computed as a weighted sum over the prediction values eh(x).val of each tree Th;
• wherein each tree Th is traversed and a corresponding set Ch of candidate exit leaves is updated during the traversal, with Ch⊆Lh, including said exit leaf eh, wherein initially Ch contains all the leaves in Lh, wherein the following further steps are executed:
• A. for each tree Th, the Boolean test of all nodes in Nh={n0,n1, . . . } are evaluated in an arbitrary order,
• B1. for a false node, the leaves in the left subtree are removed from Ch,
• B2. for a true node, the leaves in the right subtree are removed from Ch,
• C. the leftmost leaf in Ch is taken as the exit leaf eh·,
• wherein the set of candidate documents is split into blocks and the tree ensemble is split into disjoint groups, one block of documents and one block of trees being both stored in a cache memory of said computer at the same time, each block of document being scored with respect to each disjoint group.