Comparing top k lists
Comparing top k lists
复制标题
DOI：
10.1137/s0895480102412856
复制
发表时间：
2003-01-01
影响因子：
0.8
通讯作者：
Sivakumar, D
中科院分区：
文献类型：
--
作者：
Fagin, R;Kumar, R;Sivakumar, D
受几个应用程序的启发，我们在“前k个列表”之间引入了各种距离度量。这些距离测量中的一些是度量，而另一些不是。对于后两个距离度量，我们证明了它们在以下两个看似不相关的方面“几乎”是一个度量：(I)它们满足多边形(因此，三角形)不等式的一个松弛版本，以及(Ii)存在一个具有正常数倍的度量，它限定了上面和下面的度量。这不是巧合-我们证明了这两个几乎是度量的概念是相同的。基于第二个概念，我们决定。称两个距离度量是等价的，如果它们以彼此的常数倍数上下有界。我们的结果不仅应用于识别两个前k个列表之间的好的(不)相似概念，而且提出了关于一大类距离度量的秩集问题的多项式时间常因式近似算法。
Motivated by several applications, we introduce various distance measures between "top k lists." Some of these distance measures are metrics, while others are not. For each of these latter distance measures, we show that they are "almost" a metric in the following two seemingly unrelated aspects:(i) they satisfy a relaxed version of the polygonal ( hence, triangle) inequality, and(ii) there is a metric with positive constant multiples that bound 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 de. ne 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.