Abstract

Motivated by several applications, we introduce various distance measures between k lists. Some of these distance measures are metrics, while others are not. For each of these latter distance measures: we show that it is a metric in the following two seemingly unrelated aspects:step-(i) it satisfies a relaxed version of the polygonal (hence, triangle) inequality, andstep-(ii) there is a metric with positive constant multiples that bounds our measure above and below.This is not a coincidence---we show that these two notions of almost being a metric are the same. Based on the second notion, we define two distance measures to be equivalent if they are bounded above and below by constant multiples of each other. We thereby identify a large and robust equivalence class of distance measures.Besides the applications to the task of identifying good notions of (dis-)similarity between two top k lists, our results imply polynomial-time constant-factor approximation algorithms for the rank aggregation problem with respect to a large class of distance measures.

Keywords

Triangle inequalityBounded functionDistance measuresMetric (unit)MathematicsConstant (computer programming)Edit distanceEquivalence (formal languages)CombinatoricsDiscrete mathematicsClass (philosophy)Measure (data warehouse)Equivalence class (music)Computer scienceAlgorithmArtificial intelligenceData miningMathematical analysis

Affiliated Institutions

Related Publications

Publication Info

Year
2003
Type
article
Volume
17
Issue
1
Pages
28-36
Citations
765
Access
Closed

External Links

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

765
OpenAlex

Cite This

Ronald Fagin, Ravi Kumar, D. Sivakumar (2003). Comparing top k lists. Symposium on Discrete Algorithms , 17 (1) , 28-36. https://doi.org/10.5555/644108.644113

Identifiers

DOI
10.5555/644108.644113