Skip to main content
Log in

Aggregation of Partial Rankings, p-Ratings and Top-m Lists

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study the problem of aggregating partial rankings. This problem is motivated by applications such as meta-searching and information retrieval, search engine spam fighting, e-commerce, learning from experts, analysis of population preference sampling, committee decision making and more. We improve recent constant factor approximation algorithms for aggregation of full rankings and generalize them to partial rankings. Our algorithms improve constant factor approximation with respect to a family of metrics recently proposed in the context of comparing partial rankings. We pay special attention to two important types of partial rankings: the well-known top-m lists and the more general p-ratings which we define. We provide first evidence for hardness of aggregating them for constant mp.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ailon, N.: Aggregation of partial rankings, p-ratings and top-m lists. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 415–424 (2007)

  2. Ailon, N., Charikar, M.: Fitting tree metrics: Hierarchical clustering and phylogeny. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 73–82 (2005)

  3. Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 684–693 (2005)

  4. Ailon, N., Charikar, M., Newman, A.: Proofs of conjectures in ‘Aggregating inconsistent information: Ranking and clustering’. Technical Report, Princeton University, TR-719-05 (2005)

  5. Alon, N.: Ranking tournaments. SIAM J. Discrete Math. 20(1), 137–142 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  6. Arrow, K.J.: Social Choice and Individual Values. Wiley, New York (1951)

    MATH  Google Scholar 

  7. Aslam, J., Montague, M.: Condorcet fusion for improved retrieval. In: Proceedings of the 11th International Conference on Information and Knowledge Management, pp. 538–548 (2002)

  8. Borda, J.C.: Mémoire sur les élections au scrutin. Histoire de l’Académie Royale des Sciences (1781)

  9. Condorcet, M.-J.: Éssai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (1785)

  10. Coppersmith, D., Fleischer, L., Rudra, A.: Ordering by weighted number of wins gives a good ranking for weighted tournamnets. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 776–782 (2006)

  11. Diaconis, P., Graham, R.: Spearman’s footrule as a measure of disarray. J. R. Stat. Soc. Ser. B 39(2), 262–268 (1977)

    MATH  MathSciNet  Google Scholar 

  12. Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Proceedings of the Tenth International Conference on the World Wide Web (WWW10), pp. 613–622, Hong Kong (2001)

  13. Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation revisited. Manuscript (2001)

  14. Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., Vee, E.: Comparing and aggregating rankings with ties. In: Proceedings of the ACM Symposium on Principles of Database Systems (PODS), pp. 47–58 (2004)

  15. Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., Vee, E.: Comparing partial rankings. SIAM J. Discrete Math. 20(3), 628–648 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  16. Fagin, R., Kumar, R., Sivakumar, D.: Comparing top k lists. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 28–36, Baltimore (2003)

  17. Fagin, R., Kumar, R., Sivakumar, D.: Efficient similarity search and classification via rank aggregation. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 301–312, San Diego (2003)

  18. Filkov, V., Skiena, S.: Integrating microarray data by consensus clustering. In: Proceedings of International Conference on Tools with Artificial Intelligence (ICTAI), pp. 418–425, Sacramento (2003)

  19. Gionis, A., Mannila, H., Tsaparas, P.: Clustering aggregation. TKDD 1(1) (2007)

  20. Hodge, J., Klima, R.E.: The Mathematics of Voting and Elections: A Hands-On Approach. Mathematical World, vol. 22. Am. Math. Soc., Providence (2000)

    Google Scholar 

  21. Kemeny, J., Snell, J.: Mathematical Models in the Social Sciences. Blaisdell, Boston (1962). Reprinted by MIT Press, Cambridge (1972)

    MATH  Google Scholar 

  22. Kemeny, J.G.: Mathematics without numbers. Daedalus 88, 571–591 (1959)

    Google Scholar 

  23. Kendall, M., Gibbons, J.D.: Rank Correlation Methods. Arnold, Sevenoaks (1990)

    MATH  Google Scholar 

  24. Kenyon-Mathieu, C., Schudy, W.: How to rank with few errors. In: STOC’07: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pp. 95–103. Assoc. Comput. Mach., New York, 2007

    Chapter  Google Scholar 

  25. Rand, W.: Objective criteria for the evaluation of clustering methods. J. Am. Stat. Assoc. 66(336), 846–850 (1971)

    Article  Google Scholar 

  26. Strehl, A.: Relationship-based clustering and cluster ensembles for high-dimensional data mining. Ph.D. Dissertation, University of Texas at Austin, May 2002

  27. Wakabayashi, Y.: The complexity of computing medians of relations. Resenhas 3(3), 323–349 (1998)

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Nir Ailon.

Additional information

Most of this work done while author was a student in the Department of Computer Science at Princeton University, and part while a member of the Institute for Advanced Study, supported by the National Science Foundation under agreement No. DMS-0111298. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation. A preliminary version appeared in 1.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ailon, N. Aggregation of Partial Rankings, p-Ratings and Top-m Lists. Algorithmica 57, 284–300 (2010). https://doi.org/10.1007/s00453-008-9211-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-008-9211-1

Keywords

Navigation