Comparing top k lists

By Ronald Fagin, Ravi Kumar, D. Sivakumar. ACM-SIAM Symposium on Discrete Algorithms, 2003

1,094 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/d72a4c789b904af8a5a19f8b73813c95d21c1f05

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Deeper Inside PageRank (2004, methodology): “Several papers [44, 47, 48, 58, 60, 86] have provided a variety of answers to the question of comparing rank orderings, using such measures as Kendall’s Tau, rank aggregation, and set overlap.”
A survey of top-k query processing techniques in relational database systems (2008, methodology): “[Diaconis 1998; Fagin et al. 2003; Fagin et al. 2004] describe different distance measures.”
Generalized distances between rankings (2010, background): “To quantify the importance of the top few positions over the bottom ranks, the set of measures was expanded to compare only the top-k rankings, for a given value of the cut-off k [12].”
Measuring Price Discrimination and Steering on E-commerce Web Sites (2014, background): “Several studies improve on Kendall’s τ by adding per-rank weights [14,40], and by taking item similarity into account [21,39].”
Algorithms for estimating relative importance in networks (2003, methodology): “We used the K-Min (minimizing Kendall distance) metric of Fagin et al. (2003) to measure distances between the top-10 lists produced by the different relative importance algorithms.”
The Geodesic Problem in Quasimetric Spaces (2008, methodology): “1When this article was submitted, the author used the term “nearmetric” as in [8] instead of “quasimetric”.”
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments (2005, methodology): “…studied by the web-search community for measuring the speed of convergence in PageRank computations [Kamvar et al. 03b], the distortion of PageRank encodings [Haveliwala 03], and the quality of rank-aggregation methods [Fagin et al. 03b, Fagin et al. 04, Fagin et al. 03a, Dwork et al. 01].”
Rank Aggregation: Together We're Strong (2009, background): “Fagin et al [10, 11, 12] proposed a set of different distance measures between two partial rankings and a permutation and a partial ranking.”
A similarity measure for indefinite rankings (2010, methodology): “The remainder of the proof follows Fagin et al. [2003]. Consider an element x ∈ R T.”
A new rank correlation coefficient for information retrieval (2008, methodology): “[5] proposed an extension to Kendall’s τ for comparing top-k lists.”
An experimental study of the intrinsic stability of random forest variable importance measures (2016, background): “It makes sense to only analyze the top ranked features [35, 36].”
Extrapolation methods for accelerating PageRank computations (2003, background): “show in [7] that distance measures based on Kendall’sare bounded by a true metric, providing insight as to why the results of Figure 8 are to be expected.”
What is Twitter, a social network or a news media? (2010, methodology): “We compare the three rankings by the number of followers (RF ), PageRank (RPR) and the number of retweets (RRT ) in terms of Fagin et al.’s generalized Kendall’s tau [ 8 ].”
Clustering aggregation (2005, methodology): “RELATED WORK A source of motivation for our work is the literature on comparing and merging multiple rankings [Dwork et al. 2001; Fagin et al. 2003].”
Improving recommendation lists through topic diversification (2005, background): “Fagin et al. [ 7 ] propose metrics for measuring the distance between top-N lists, i.e., inter-list similarity metrics, in order to evaluate the quality of merged ranks.”
Distributed top-k monitoring (2003, background): “Work on combining ranked lists on the web [13, 15] focuses on combining relative orderings from multiple lists and does not perform numeric aggregation of values across multiple data sources.”