Comparing top k lists Export

@article{Fagin:Comparing, abstract = {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 it is "almost" 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.}, address = {Philadelphia, PA, USA}, author = {Fagin, Ronald and Kumar, Ravi and Sivakumar, D.}, booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms}, citeulike-article-id = {882121}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=644108.644113}, comment = {Proposes several vairations of Kendall's tau for top k lists where the 2 lists do not necessarily share all their elements. They applied one variation to comparing search engine results.}, isbn = {0-89871-538-5}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {kendall-tau, search-engine-results-comparison}, location = {Baltimore, Maryland}, number = {1}, pages = {134--160}, posted-at = {2006-10-02 22:49:01}, priority = {0}, publisher = {Society for Industrial and Applied Mathematics}, title = {Comparing top k lists}, url = {http://portal.acm.org/citation.cfm?id=644108.644113}, volume = {17}, year = {2003} }

TY - JOUR ID - Fagin:Comparing L3 - citeulike-article-id:882121 JF - SIAM Journal on Discrete Mathematics N2 - 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 it is "almost" 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. VL - 17 PB - Society for Industrial and Applied Mathematics IS - 1 CY - Baltimore, Maryland T2 - SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms SN - 0-89871-538-5 SP - 134 TI - Comparing top k lists EP - 160 AD - Philadelphia, PA, USA KW - kendall-tau KW - search-engine-results-comparison N1 - Proposes several vairations of Kendall's tau for top k lists where the 2 lists do not necessarily share all their elements. They applied one variation to comparing search engine results. AU - Fagin, Ronald AU - Kumar, Ravi AU - Sivakumar, D PY - 2003/// UR - http://portal.acm.org/citation.cfm?id=644108.644113 ER -