2010 | OriginalPaper | Buchkapitel
Top-d Rank Aggregation in Web Meta-search Engine
(Extended Abstract)
verfasst von : Qizhi Fang, Han Xiao, Shanfeng Zhu
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper, we consider the rank aggregation problem for information retrieval over Web making use of a kind of metric, the coherence, which considers both the normalized Kendall-
τ
distance and the size of overlap between two partial rankings. In general, the top-
d
coherence aggregation problem is defined as: given collection of partial rankings Π = {
τ
1
,
τ
2
, ⋯ ,
τ
K
}, how to find a final ranking
π
with specific length
d
, which maximizes the total coherence
$\Phi(\pi,\Pi)=\sum_{i=1}^K \Phi(\pi,\tau_i)$
. The corresponding complexity and algorithmic issues are discussed in this paper. Our main technical contribution is a polynomial time approximation scheme (PTAS) for a restricted top-
d
coherence aggregation problem.