An axiomatic approach to constructing distances for rank comparison and aggregation

Farzad Farnoud Hassanzadeh, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review

Abstract

We propose a new family of distance measures on rankings, derived through an axiomatic approach, that consider the nonuniform relevance of the top and bottom of ordered lists and similarities between candidates. The proposed distance functions include specialized weighted versions of the Kendall τ distance and the Cayley distance, and are suitable for comparing rankings in a number of applications, including information retrieval and rank aggregation. In addition to proposing the distance measures and providing the theoretical underpinnings for their applications, we also analyze algorithmic and computational aspects of weighted distance-based rank aggregation. We present an aggregation method based on approximating weighted distance measures by a generalized version of Spearman's footrule distance as well as a Markov chain method inspired by PageRank, where transition probabilities of the Markov chain reflect the chosen weighted distances.

Original languageEnglish (US)
Article number6872786
Pages (from-to)6417-6439
Number of pages23
JournalIEEE Transactions on Information Theory
Volume60
Issue number10
DOIs
StatePublished - Oct 1 2014

Keywords

  • PageRank
  • Weighted Kendall distance
  • collaborative filtering
  • information retrieval
  • positional relevance
  • rank aggregation
  • similarity
  • statistics
  • top-vs-bottom

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'An axiomatic approach to constructing distances for rank comparison and aggregation'. Together they form a unique fingerprint.

Cite this