Abstract: This paper studies the rank fusion problem via voting algorithms. Based on two widely discussed classical voting rules: Borda and Condorcet, some elimination voting algorithms and their variants, including Kemeny method, are analyzed in a graph theoretic approach. Because Kemeny ranking is a NP-hard problem, a new heuristic elimination voting algorithm is proposed. Some experiments are carried out on TREC data for evaluating these voting algorithms on rank fusion. Experiments show that these elimination algorithms have comparable performance with Borda algorithm, and sometimes outperform it.

Key words: rank fusion, voting model, metasearch, information retrieval

摘要： 排序合成问题是元搜索引擎研究的一个重要方面。该文分析了基于投票模型的排序合成问题。在讨论2个常用的投票规则Borda和Condorcet的基础上，介绍了用图论算法实现的淘汰投票算法，包括Kemeny算法。针对Kemeny算法是NP-hard问题，提出了一种易于实现的启发式淘汰投票算法，并且利用TREC数据集进行实验比较这些方法。实验结果表明，淘汰投票算法与Borda算法执行效果相当，有时甚至超过Borda算法。

关键词: 排序合成, 投票模型, 元搜索, 信息检索

CLC Number: 

• TP391