Abstract
Ranked lists are encountered in research and daily life and it is often of interest to compare these lists even when they are incomplete or have only some members in common. An example is document rankings returned for the same query by different search engines. A measure of the similarity between incomplete rankings should handle nonconjointness, weight high ranks more heavily than low, and be monotonic with increasing depth of evaluation; but no measure satisfying all these criteria currently exists. In this article, we propose a new measure having these qualities, namely rank-biased overlap (RBO). The RBO measure is based on a simple probabilistic user model. It provides monotonicity by calculating, at a given depth of evaluation, a base score that is non-decreasing with additional evaluation, and a maximum score that is nonincreasing. An extrapolated score can be calculated between these bounds if a point estimate is required. RBO has a parameter which determines the strength of the weighting to top ranks. We extend RBO to handle tied ranks and rankings of different lengths. Finally, we give examples of the use of the measure in comparing the results produced by public search engines and in assessing retrieval systems in the laboratory.
- Bar-Ilan, J. 2005. Comparing rankings of search results on the Web. Inform. Proc. Manag. 41, 1511--1519. Google ScholarDigital Library
- Bar-Ilan, J., Mat-Hassan, M., and Levene, M. 2006. Methods for comparing rankings of search engine results. Comput. Netw. 50, 10 (July), 1448--1463. Google ScholarDigital Library
- Blest, D. C. 2000. Rank correlation—an alternative measure. Australian and New Zealand J. Statis. 42, 1, 101--111.Google ScholarCross Ref
- Buckley, C. 2004. Topic prediction based on comparative retrieval rankings. In Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, M. Sanderson, K. Järvelin, J. Allan, and P. Bruza, Eds. 506--507. Google ScholarDigital Library
- Carterette, B. 2009. On rank correlation and the distance between rankings. In Proceedings of the 32nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, J. Allan, J. Aslam, M. Sanderson, C. Zhai, and J. Zobel, Eds. 436--443. Google ScholarDigital Library
- Cliff, N. 1996. Ordinal Methods for Behavioural Data Analysis. Lawrence Erlbaum Associates.Google Scholar
- Fagin, R., Kumar, R., and Sivakumar, D. 2003. Comparing top k lists. SIAM J. Discrete Mathem. 17, 1, 134--160. Google ScholarDigital Library
- Gibbons, J. D. and Chakraborti, S. 2003. Nonparametric Statistical Inference 4th Ed. CRC.Google Scholar
- Goodman, L. A. and Kruskal, W. H. 1954. Measures of association for cross classifications. J. Am. Statis. Assoc. 49, 268, 732--764.Google Scholar
- Iman, R. L. and Conover, W. J. 1987. A measure of top-down correlation. Technometrics 29, 351--357. Google ScholarDigital Library
- Järvelin, K. and Kekäläinen, J. 2002. Cumulated gain-based evaluation of IR techniques. ACM Trans. Inform. Syst. 20, 4, 422--446. Google ScholarDigital Library
- Kendall, M. G. 1948. Rank Correlation Methods 1st Ed. Charles Griffin, London.Google Scholar
- Knuth, D. E. 1997. The Art of Computer Programming, Vol. I: Fundamental Algorithms. 3rd Ed. Addison Wesley, Reading, MA. Google ScholarDigital Library
- Lester, N., Moffat, A., Webber, W., and Zobel, J. 2005. Space-limited ranked query evaluation using adaptive pruning. In Proceedings of the 6th International Conference on Web Informations Systems. A. H. Ngu, M. Kitsuregawa, E. J. Neuhold, J.-Y. Chung, and Q. Z. Sheng, Eds. Lecture Notes in Computer Science, vol. 3806, 470--477. Google ScholarDigital Library
- Melucci, M. 2007. On rank correlation in information retrieval evaluation. SIGIR Forum 41, 1, 18--33. Google ScholarDigital Library
- Melucci, M. 2009. Weighted rank correlation in information retrieval evaluation. In Proceedings of the 5th Asia Information Retrieval Symposium, G. G. Lee, D. Song, C.-Y. Lin, A. Aizawa, K. Kuriyama, M. Yoshioka, and T. Sakai, Eds. Lecture Notes in Computer Science, vol. 5839, 75--86. Google ScholarDigital Library
- Moffat, A. and Zobel, J. 2008. Rank-biased precision for measurement of retrieval effectiveness. ACM Trans. Inform. Syst. 27, 1, 1--27. Google ScholarDigital Library
- Quade, D. and Salama, I. A. 1992. A survey of weighted rank correlation. In Order Statistics and Nonparametrics: Theory and Applications, P. K. Sen and I. A. Salama, Eds. Elsevier, 213--224.Google Scholar
- Shieh, G. S. 1998. A weighted Kendall's tau statistic. Statist. Probability Lett. 39, 17--24.Google ScholarCross Ref
- Tarsitano, A. 2002. Nonlinear rank correlation. Departmental working paper, Universitò degli studi della Calabria.Google Scholar
- Wu, S. and Crestani, F. 2003. Methods for ranking information retrieval systems without relevance judgments. In Proceedings of the ACM Symposium on Applied Computing (SAC). 811--816. Google ScholarDigital Library
- Yilmaz, E., Aslam, J. A., and Robertson, S. 2008. A new rank correlation coefficient for information retrieval. In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, S.-H. Myaeng, D. W. Oard, F. Sebastiani, T.-S. Chua, and M.-K. Leong, Eds. 587--594. Google ScholarDigital Library
- Zhai, C. and Lafferty, J. 2004. A study of smoothing methods for language models applied to information retrieval. ACM Trans. Inform. Syst. 22, 2, (Apr.). 179--214. Google ScholarDigital Library
Index Terms
- A similarity measure for indefinite rankings
Recommendations
Comparing rankings of search results on the Web
Special issue: InfometricsThe Web has become an information source for professional data gathering. Because of the vast amounts of information on almost all topics, one cannot systematically go over the whole set of results, and therefore must rely on the ordering of the results ...
What's Going on in Search Engine Rankings?
AINAW '08: Proceedings of the 22nd International Conference on Advanced Information Networking and Applications - WorkshopsMany people use search engines every day to retrieve documents from the Web. Although the social influence of search engine rankings has become significant, ranking algorithms are not disclosed. In this paper, we have investigated three major search ...
Methods for comparing rankings of search engine results
Web dynamicsIn this paper we present a number of measures that compare rankings of search engine results. We apply these measures to five queries that were monitored daily for two periods of 14 or 21 days each. Rankings of the different search engines (Google, ...
Comments