{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:57:31Z","timestamp":1764997051771},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,7]]},"abstract":"<jats:p>The problem of aggregating multiple rankings into one consensus ranking is an active research topic especially in the database community. Various studies have implemented methods for rank aggregation and may have come up with contradicting conclusions upon which algorithms work best. Comparing such results is cumbersome, as the original studies mixed different approaches and used very different evaluation datasets and metrics. Additionally, in real applications, the rankings to be aggregated may not be permutations where elements are strictly ordered, but they may have ties where some elements are placed at the same position. However, most of the studies have not considered ties.<\/jats:p>\n          <jats:p>This paper introduces the first large scale study of algorithms for rank aggregation with ties. More precisely, (i) we review rank aggregation algorithms and determine whether or not they can handle ties; (ii) we propose the first implementation to compute the exact solution of the Rank Aggregation with ties problem; (iii) we evaluate algorithms for rank aggregation with ties on a very large panel of both real and carefully generated synthetic datasets; (iv) we provide guidance on the algorithms to be favored depending on dataset features.<\/jats:p>","DOI":"10.14778\/2809974.2809982","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T14:37:34Z","timestamp":1438267054000},"page":"1202-1213","source":"Crossref","is-referenced-by-count":27,"title":["Rank aggregation with ties"],"prefix":"10.14778","volume":"8","author":[{"given":"Bryan","family":"Brancotte","sequence":"first","affiliation":[{"name":"CNRS UMR, Univ. Paris-Sud, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bo","family":"Yang","sequence":"additional","affiliation":[{"name":"CNRS UMR, Univ. Paris-Sud, France and Wuhan Univ., Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Blin","sequence":"additional","affiliation":[{"name":"Univ. Bordeaux, Talence, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarah","family":"Cohen-Boulakia","sequence":"additional","affiliation":[{"name":"CNRS UMR, Univ. Paris-Sud, France and Inria, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alain","family":"Denise","sequence":"additional","affiliation":[{"name":"CNRS UMR, Univ. Paris-Sud, France and CNRS, Univ. Paris-Sud, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvie","family":"Hamel","sequence":"additional","affiliation":[{"name":"CNRS UMR, Univ. Paris-Sud, France and Univ. Montr\u00e9al - Qu\u00e9bec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9211-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2011.08.008"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1639714.1639782"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-013-9236-y"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.07.005"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.088"},{"key":"e_1_2_1_8_1","first-page":"657","volume-title":"M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l'academie royal des sciences","author":"Borda J.","unstructured":"J. Borda . M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l'academie royal des sciences , pages 657 -- 664 , 1781. J. Borda. M\u00e9moire sur les \u00e9lections au scrutin. Histoire de l'academie royal des sciences, pages 657--664, 1781."},{"key":"e_1_2_1_9_1","volume-title":"Rank aggregation with ties is at least as difficult as rank aggregation without ties. Internal report","author":"Brancotte B.","unstructured":"B. Brancotte and R. Milosz . Rank aggregation with ties is at least as difficult as rank aggregation without ties. Internal report , Univ. Paris-Sud - France . B. Brancotte and R. Milosz. Rank aggregation with ties is at least as difficult as rank aggregation without ties. Internal report, Univ. Paris-Sud - France."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08590-6_13"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00249646"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032397.2032404"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1537601"},{"key":"e_1_2_1_14_1","first-page":"620","volume-title":"Proceedings of the 21st national conference on Artificial intelligence -","volume":"1","author":"Conitzer V.","year":"2006","unstructured":"V. Conitzer , A. Davenport , and J. Kalagnanam . Improved bounds for computing kemeny rankings . In Proceedings of the 21st national conference on Artificial intelligence - Volume 1 , pages 620 -- 626 . AAAI Press , 2006 . V. Conitzer, A. Davenport, and J. Kalagnanam. Improved bounds for computing kemeny rankings. In Proceedings of the 21st national conference on Artificial intelligence - Volume 1, pages 620--626. AAAI Press, 2006."},{"key":"e_1_2_1_15_1","volume-title":"A reasonable social welfare function","author":"Copeland A. H.","year":"1951","unstructured":"A. H. Copeland . A reasonable social welfare function . University of Michigan Seminar on Applications of Mathematics to the social sciences , 1951 . A. H. Copeland. A reasonable social welfare function. University of Michigan Seminar on Applications of Mathematics to the social sciences, 1951."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109642"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1597148.1597260"},{"key":"e_1_2_1_18_1","volume-title":"Combining results of microarray experiments: a rank aggregation approach. Statistical Applications in Genetics and Molecular Biology, 5(1)","author":"DeConde R. P.","year":"2006","unstructured":"R. P. DeConde , S. Hawley , S. Falcon , N. Clegg , B. Knudsen , and R. Etzioni . Combining results of microarray experiments: a rank aggregation approach. Statistical Applications in Genetics and Molecular Biology, 5(1) , 2006 . R. P. DeConde, S. Hawley, S. Falcon, N. Clegg, B. Knudsen, and R. Etzioni. Combining results of microarray experiments: a rank aggregation approach. Statistical Applications in Genetics and Molecular Biology, 5(1), 2006."},{"key":"e_1_2_1_19_1","series-title":"Series B (Methodological)","first-page":"262","volume-title":"Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society","author":"Diaconis P.","year":"1977","unstructured":"P. Diaconis and R. L. Graham . Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society . Series B (Methodological) , pages 262 -- 268 , 1977 . P. Diaconis and R. L. Graham. Spearman's footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological), pages 262--268, 1977."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372165"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055568"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063088X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102412856"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872795"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90226-7"},{"key":"e_1_2_1_26_1","volume-title":"MuPAD-Combinat, an open-source package for research in algebraic combinatorics. S\u00e9m. Lothar. Combin., 51:Art. B51z, 70","author":"Hivert F.","year":"2004","unstructured":"F. Hivert and N. M. Thi\u00e9ry . MuPAD-Combinat, an open-source package for research in algebraic combinatorics. S\u00e9m. Lothar. Combin., 51:Art. B51z, 70 pp. (electronic), 2004 . F. Hivert and N. M. Thi\u00e9ry. MuPAD-Combinat, an open-source package for research in algebraic combinatorics. S\u00e9m. Lothar. Combin., 51:Art. B51z, 70 pp. (electronic), 2004."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732998"},{"issue":"4","key":"e_1_2_1_28_1","first-page":"577","article-title":"Mathematics without numbers","volume":"88","author":"Kemeny J. G.","year":"1959","unstructured":"J. G. Kemeny . Mathematics without numbers . Daedalus , 88 ( 4 ): 577 -- 591 , 1959 . J. G. Kemeny. Mathematics without numbers. Daedalus, 88(4):577--591, 1959.","journal-title":"Daedalus"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/30.1-2.81"},{"key":"e_1_2_1_30_1","volume-title":"Consensus ranking under the exponential model. arXiv preprint arXiv:1206.5265","author":"Meila M.","year":"2012","unstructured":"M. Meila , K. Phadnis , A. Patterson , and J. A. Bilmes . Consensus ranking under the exponential model. arXiv preprint arXiv:1206.5265 , 2012 . M. Meila, K. Phadnis, A. Patterson, and J. A. Bilmes. Consensus ranking under the exponential model. arXiv preprint arXiv:1206.5265, 2012."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2791220.2791224"},{"key":"e_1_2_1_32_1","series-title":"Genome Informatics Series","first-page":"506","volume-title":"Rank aggregation method for biological databases","author":"Sese J.","year":"2001","unstructured":"J. Sese and S. Morishita . Rank aggregation method for biological databases . Genome Informatics Series , pages 506 -- 507 , 2001 . J. Sese and S. Morishita. Rank aggregation method for biological databases. Genome Informatics Series, pages 506--507, 2001."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732988"},{"key":"e_1_2_1_34_1","volume-title":"CIDR","author":"Stoyanovich J.","year":"2013","unstructured":"J. Stoyanovich , S. Amer-Yahia , S. B. Davidson , M. Jacob , T. Milo , Understanding local structure in ranked datasets . In CIDR , 2013 . J. Stoyanovich, S. Amer-Yahia, S. B. Davidson, M. Jacob, T. Milo, et al. Understanding local structure in ranked datasets. In CIDR, 2013."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0385"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2809974.2809982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:47:19Z","timestamp":1672224439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2809974.2809982"}},"subtitle":["experiments and analysis"],"short-title":[],"issued":{"date-parts":[[2015,7]]},"references-count":35,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2015,7]]}},"alternative-id":["10.14778\/2809974.2809982"],"URL":"https:\/\/doi.org\/10.14778\/2809974.2809982","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,7]]}}}