Comparing and aggregating rankings with ties

摘要: Rank aggregation has recently been proposed as a useful abstraction that several applications, including meta-search, synthesizing rank functions from multiple indices, similarity search, and classification. In database applications (catalog searches, fielded parametric etc.), the rankings are produced by sorting an underlying according to various fields. Typically, there number of fields each have very few distinct values, hence corresponding many ties in them. Known methods for poorly suited this context, difficulties can be traced back fact we do not sound mathematical principles compare two partial rankings, is, allow ties.In work, provide comprehensive picture how We propose metrics present algorithms efficiently compute them, prove they within constant multiples other. Based on these concepts, formulate problems develop highly efficient algorithm top elements near-optimal rankings. model access is suitable databases, our reads essentially ranking necessary determine winner(s).