Trimming the complexity of Ranking by Pairwise Comparison

In computer science research, and more specifically in bioinformatics, the size of databases never stops to increase. This can be an issue when trying to answer questions that imply algorithms in nonlinear polynomial time with regards to the number of objects in the database, the number of attributes or the number of associated labels per objects. This is the case of the Ranking by Pairwise Comparison (RPC) algorithm. This algorithm builds a model which is able to predict the label preference for a given object, but the computation needs to be performed in an order of N(N−1)2 in terms of the number N of labels. Indeed, a pairwise comparator model is needed for each possible pair of labels. Our hypothesis is that a significant part of the set of comparators often con-tains redundancy and/or noise, so that trimming the set could be beneficiary. We implemented several methods, starting from the simplest one, which merely chooses a set of T comparators (T < N(N−1)2) at random, to a more comple