Training linear ranking SVMs in linearithmic time using red-black trees

Learning to rank has been a task of significant interest during the recent years. The ranking problem has been largely motivated by applications in areas such as web search and recommender systems. Due to the large amounts of data available in these domains, it is necessary for the used algorithms to scale well, preferably close to linear time methods are needed. For a detailed introduction to the topic of learning to rank, we refer to (Liu, 2009; Fürnkranz and Hüllermeier, 2011). In this work we assume the so-called scoring setting, where each data instance is associated with a utility score reflecting its goodness with respect to the ranking criterion. A successful approach for learning ranking functions has been to consider pairwise preferences (Fürnkranz and Hüllermeier, 2005). In this setting, the aim is to minimize the number of pairwise mis-orderings in the ranking produced when ordering a set of examples according to predicted utility scores. A number of machine learning algorithms optimizing relaxations of this criterion have been proposed, such as the RankBoost (Freund et al., 2003), RankNet (Burges et al., 2005), RankRLS (Pahikkala et al., 2007, 2009), and the subject of this study, the ranking support vector machine (RankSVM) algorithm (Herbrich et al., 1999; Joachims, 2002). The original solution proposed for RankSVM optimization was to train a support vector machine (SVM) classifier on pairs of data examples.