skip to main content
10.1145/1772690.1772749acmotherconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Generalized distances between rankings

Published: 26 April 2010 Publication History

Abstract

Spearman's footrule and Kendall's tau are two well established distances between rankings. They, however, fail to take into account concepts crucial to evaluating a result set in information retrieval: element relevance and positional information. That is, changing the rank of a highly-relevant document should result in a higher penalty than changing the rank of an irrelevant document; a similar logic holds for the top versus the bottom of the result ordering. In this work, we extend both of these metrics to those with position and element weights, and show that a variant of the Diaconis-Graham inequality still holds - the generalized two measures remain within a constant factor of each other for all permutations.
We continue by extending the element weights into a distance metric between elements. For example, in search evaluation, swapping the order of two nearly duplicate results should result in little penalty, even if these two are highly relevant and appear at the top of the list. We extend the distance measures to this more general case and show that they remain within a constant factor of each other.
We conclude by conducting simple experiments on web search data with the proposed measures. Our experiments show that the weighted generalizations are more robust and consistent with each other than their unweighted counter-parts.

References

[1]
R. Agrawal, S. Gollapudi, A. Halverson, and S. Ieong. Diversifying search results. In Proc. 2nd WSDM, pages 5--14, 2009.
[2]
N. Ailon, M. Charikar, and A. Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5), 2008.
[3]
C. Buckley and E. Voorhees. Retrieval evaluation with incomplete information. In Proc. 27th SIGIR, pages 25--32, 2004.
[4]
B. Carterette. On rank correlation and the distance between rankings. In Proc. 32nd SIGIR, pages 436--443, 2009.
[5]
O. Chapelle, D. Metlzer, Y. Zhang, and P. Grinspan. Expected reciprocal rank for graded relevance. In Proc. 18th CIKM, pages 621--630, 2009.
[6]
N. Craswell, O. Zoeter, M. Taylor, and B. Ramsey. An experimental comparison of click position--bias models. In Proc. 1st WSDM, pages 87--94, 2008.
[7]
P. D'Alberto and A. Dasdan. Content-based search engine rank correlation. Manuscript, 2009.
[8]
P. Diaconis. Group Representation in Probability and Statistics. Number 11 in IMS Lecture Series. Institute of Mathematical Statistics, 1988.
[9]
P. Diaconis and R. Graham. Spearman footrule as a measure of disarray. Journal of the Royal Statistical Society B (Methodological), 39(2):262--268, 1977.
[10]
C. Dwork, R. Kumar, M. Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proc. 10th WWW, pages 613--622, 2001.
[11]
R. Fagin, R. Kumar, M. Mahdian, D. Sivakumar, and E. Vee. Comparing partial rankings. SIAM J. Discrete Math., 20(3):628--648, 2006.
[12]
R. Fagin, R. Kumar, and D. Sivakumar. Comparing top k lists. In Proc. 14th SODA, pages 28--36, 2003.
[13]
R. Fagin, R. Kumar, and D. Sivakumar. Efficient similarity search and classification via rank aggregation. In Proc. SIGMOD, pages 301--312, 2003.
[14]
K. Jarvelin and J. Kekalainen. IR evaluation methods for retrieving highly relevant documents. In Proc. 23rd SIGIR, pages 41--48, 2000.
[15]
M. G. Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81--93, 1938.
[16]
C. Kenyon-Mathieu and W. Schudy. How to rank with few errors. In Proc. 39th STOC, pages 95--103, 2007.
[17]
D. Sculley. Rank aggregation for similar items. In SDM, 2007.
[18]
G. Shieh, Z. Bai, and W. Tsai. Rank tests for independence - with a weighted contamination alternative. Statistica Sinica, 10:577--593, 2000.
[19]
G. S. Shieh. A weighted Kendall's tau statistic. Statistics & Probability Letters, 39(1):17--24, 1998.
[20]
C. Spearman. The proof and measurement of association between two things. The American Journal of Psychology, 15(1):72--101, 1904.
[21]
E. Yilmaz, J. A. Aslam, and S. Robertson. A new rank correlation coefficient for information retrieval. In Proc. 31st SIGIR, pages 587--594, 2008.

Cited By

View all
  • (2025)Considerations for Implementation of Model‐Based Systems Engineering in Different Sectors and System Types Based on Academic LiteratureSystems Engineering10.1002/sys.21804Online publication date: 25-Jan-2025
  • (2024)A graph theoretic approach for preference learning with feature informationProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702822(3138-3158)Online publication date: 15-Jul-2024
  • (2024)Racing on the negative forceProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699137(4229-4246)Online publication date: 14-Aug-2024
  • Show More Cited By

Index Terms

  1. Generalized distances between rankings

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Other conferences
      WWW '10: Proceedings of the 19th international conference on World wide web
      April 2010
      1407 pages
      ISBN:9781605587998
      DOI:10.1145/1772690

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 26 April 2010

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. kendall's tau
      2. metrics
      3. permutation distances
      4. spearman footrule

      Qualifiers

      • Research-article

      Conference

      WWW '10
      WWW '10: The 19th International World Wide Web Conference
      April 26 - 30, 2010
      North Carolina, Raleigh, USA

      Acceptance Rates

      Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)91
      • Downloads (Last 6 weeks)8
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2025)Considerations for Implementation of Model‐Based Systems Engineering in Different Sectors and System Types Based on Academic LiteratureSystems Engineering10.1002/sys.21804Online publication date: 25-Jan-2025
      • (2024)A graph theoretic approach for preference learning with feature informationProceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence10.5555/3702676.3702822(3138-3158)Online publication date: 15-Jul-2024
      • (2024)Racing on the negative forceProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699137(4229-4246)Online publication date: 14-Aug-2024
      • (2024)Optimal Majority Rules and Quantitative Condorcet Properties of Setwise Kemeny Voting SchemesProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663180(2420-2422)Online publication date: 6-May-2024
      • (2024)Retrieving Data Permutations From Noisy Observations: AsymptoticsIEEE Transactions on Information Theory10.1109/TIT.2023.334803270:4(2999-3017)Online publication date: Apr-2024
      • (2024)Bridging the Gap: Multi-Level Cross-Modality Joint Alignment for Visible-Infrared Person Re-IdentificationIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2024.337725234:8(7683-7698)Online publication date: Aug-2024
      • (2024)CLIMBER: Pivot-Based Approximate Similarity Search Over Big Data Series2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00301(3933-3946)Online publication date: 13-May-2024
      • (2024)MRSL: a causal network pruning algorithm based on GWAS summary dataBriefings in Bioinformatics10.1093/bib/bbae08625:2Online publication date: 14-Mar-2024
      • (2024)A Novel Class of Unfolding Models for Binary Preference DataPolitical Analysis10.1017/pan.2024.11(1-17)Online publication date: 30-Sep-2024
      • (2024)Sample diversity selection strategy based on label distribution morphology for active label distribution learningPattern Recognition10.1016/j.patcog.2024.110322150(110322)Online publication date: Jun-2024
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      EPUB

      View this article in ePub.

      ePub

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media