A similarity measure for indefinite rankings

ACM Transactions on Information Systems - Tập 28 Số 4 - Trang 1-38 - 2010
William Webber1, Alistair Moffat1, Justin Zobel1
1The University of Melbourne, Australia, Victoria, Australia#TAB#

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

10.1016/j.ipm.2005.03.008

10.1016/j.comnet.2005.10.020

10.1111/1467-842X.00110

10.1145/1008992.1009093

10.1145/1571941.1572017

Cliff , N. 1996. Ordinal Methods for Behavioural Data Analysis . Lawrence Erlbaum Associates . Cliff, N. 1996. Ordinal Methods for Behavioural Data Analysis. Lawrence Erlbaum Associates.

10.1137/S0895480102412856

Gibbons J. D. and Chakraborti S. 2003. Nonparametric Statistical Inference 4th Ed. CRC. Gibbons J. D. and Chakraborti S. 2003. Nonparametric Statistical Inference 4th Ed. CRC.

Goodman , L. A. and Kruskal , W. H. 1954 . Measures of association for cross classifications . J. Am. Statis. Assoc. 49 , 268, 732--764. Goodman, L. A. and Kruskal, W. H. 1954. Measures of association for cross classifications. J. Am. Statis. Assoc. 49, 268, 732--764.

10.2307/1269344

10.1145/582415.582418

Kendall , M. G. 1948. Rank Correlation Methods 1 st Ed. Charles Griffin , London . Kendall, M. G. 1948. Rank Correlation Methods 1st Ed. Charles Griffin, London.

Knuth , D. E. 1997. The Art of Computer Programming , Vol. I : Fundamental Algorithms . 3 rd Ed. Addison Wesley , Reading, MA . Knuth, D. E. 1997. The Art of Computer Programming, Vol. I: Fundamental Algorithms. 3rd Ed. Addison Wesley, Reading, MA.

10.1007/11581062_37

10.1145/1273221.1273223

10.1007/978-3-642-04769-5_7

10.1145/1416950.1416952

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. 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.

10.1016/S0167-7152(98)00006-6

Tarsitano A. 2002. Nonlinear rank correlation. Departmental working paper Universitò degli studi della Calabria. Tarsitano A. 2002. Nonlinear rank correlation. Departmental working paper Universitò degli studi della Calabria.

10.1145/952532.952693

10.1145/1390334.1390435

10.1145/984321.984322

Thông tin
Thông tin xuất bản

ACM Transactions on Information Systems

Tập 28 Số 4

1-38

Thông tin tác giả