Basser Seminar Series

A Similarity Measure for Indefinite Rankings

Speaker: Professor Alistair Moffat
The University of Melbourne

Time: Wednesday 7 September 2011, 11:00am-12:00pm
Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1

Add seminar to my diary


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 metric designed to measure the similarity between incomplete rankings should handle non-conjointness, weight high ranks more heavily than low, and be monotonic with increasing depth of evaluation. Surprisingly, no such metrics exist. In this article, we propose a new measure having these qualities, rank-biased overlap (RBO), based on a simple probabilistic user model. The RBO measure 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 non-increasing. 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. (This work was undertaken with William Webber and Justin Zobel, and published in ACM Transactions on Information Systems, November 2010.)

Speaker's biography

Professor Alistair Moffat is Head of the Department of Computer Science and Software Engineering at the University of Melbourne, where he has been a member of the academic staff for nearly 25 years. Alistair's research interests have spanned text and index compression, information retrieval and web search algorithms, string sorting and search algorithms, and, most recently, algorithmic measurement. Alistair is an author of three books and more than 150 refereed papers.