CaltechAUTHORS
  A Caltech Library Service

An Axiomatic Approach to Constructing Distances for Rank Comparison and Aggregation

Farnoud, Farzad and Milenkovic, Olgica (2014) An Axiomatic Approach to Constructing Distances for Rank Comparison and Aggregation. IEEE Transactions on Information Theory, 60 (10). pp. 6417-6439. ISSN 0018-9448. http://resolver.caltech.edu/CaltechAUTHORS:20141023-103733565

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20141023-103733565

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/TIT.2014.2345760 DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6872786PublisherArticle
Additional Information:© 2014 IEEE. Manuscript received December 6, 2012; revised March 11, 2014; accepted June 29, 2014. Date of publication August 7, 2014; date of current version September 11, 2014. This work was supported in part by the National Science Foundation under Grant CCF-0821910 and Grant CCF-0809895, in part by the Emerging Frontiers for Science of Information Center under Grant CCF 0939370, and in part by an Air Force Office of Scientific Research Complex Networks Grant. This paper was presented at the 2012 International Conference on Signal Processing and Communications, 2012 Annual International Conference on Information Theory and Applications, and 2013 IEEE Information Theory and Workshop. The authors are grateful to Tzu-Yueh Tseng for his help with generating the numerical and simulation results, to Behrouz Touri, Eitan Yaakobi and Michael Langberg for many useful discussions, and to the anonymous reviewers for insightful comments that greatly improved the exposition of the work.
Funders:
Funding AgencyGrant Number
NSFCCF-0821910
NSFCCF-0809895
NSFCCF 0939370
Air Force Office of Scientific Research (AFOSR)UNSPECIFIED
Subject Keywords:Weighted Kendall distance; positional relevance; top-vs-bottom; similarity; rank aggregation; information retrieval; statistics; collaborative filtering; PageRank
Record Number:CaltechAUTHORS:20141023-103733565
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20141023-103733565
Official Citation:Farnoud, F.; Milenkovic, O., "An Axiomatic Approach to Constructing Distances for Rank Comparison and Aggregation," Information Theory, IEEE Transactions on , vol.60, no.10, pp.6417,6439, Oct. 2014 doi: 10.1109/TIT.2014.2345760 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6872786&isnumber=6895347
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:50730
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:23 Oct 2014 18:58
Last Modified:23 Oct 2014 18:58

Repository Staff Only: item control page