Revisiting Optimal Rank Aggregation: A Dynamic Programming Approach

Our paper "Revisiting Optimal Rank Aggregation: A Dynamic Programming Approach", withShayan A Tabrizi, Javid Dadashkarimi, Hasan Nasr Esfahani, and Azadeh Shakery, has been accepted as a short paper at the ACM SIGIR International Conference on the Theory of Information Retrieval. \o/

ICTIR2015_PosterRank aggregation, that is merging multiple ranked lists, is a pivotal challenge in many information retrieval (IR) systems, especially in distributed IR and multilingual IR. Typically, rank aggregation in IR is conducted for two different purposes:

  1. Aggregating ranked lists of a document set ranked by different ranking methods.
  2. Aggregating ranked lists of different document sets ranked by the same ranking method

Approaches that aim to solve the first kind of aggregation problem, try to take advantage of the strengths of "different methods" and overcome their weaknesses by aggregating (a.k.a. fusing) their results. On the other hand, approaches in the second group try to take advantage of “different sources” by combining their results in a single output (e.g., in distributed IR and multilingual IR). In this research, by “rank aggregation”, we refer to the second problem.

From the evaluation point of view, being able to calculate the upper bound of the performance of the final aggregated list lays the ground for evaluating different aggregation strategies, independently. In this paper, we propose an algorithm based on dynamic programming which, using relevancy information, obtains the aggregated list with the maximum performance that could be possibly achieved by any aggregation strategy. We also provide a detailed proof of the optimality of the result of the algorithm. Furthermore, we demonstrate that the previously proposed algorithm fails to reach the optimal result in many circumstances, due to its greedy essence.

For more details, please read the following paper:

Leave a Reply

Your email address will not be published. Required fields are marked *