Introduction

Search engines effectiveness can be measured by analyzing their visible outcomes which are lists of documents ranked in descending order of relevance to a given topic. In this context, the correlation among rankings can be used to assess the search engines effectiveness; in fact, when one of the two rankings is the ideal one -i.e. the best obtainable result in a laboratory based evaluation -the correlation between two rankings becomes a measure of effectiveness. A high correlation between a ranking under evaluation and the ideal indicates a good behavior of the search engine being tested. Two standard de-facto measures of distance are the Spearman foot rule [6] and the Kendall rank distance [5]. Both measures are very easy to calculate and to interpret, but they lack some properties when it comes to evaluate search engines effectiveness. A review and a classification of ranking similarity measures (including extensions of the Spearman foot rule and the Kendall rank distance) has been presented by Webber et alii in [7]. This classification is based on two main properties: conjointness and weightedness. Conjointness is the property of dealing with complete (conjoint) or partial (nonconjoint) rankings; weightedness is the property of being able (weighted) or not being able (unweighted) to weight misplacements at the top of the list more than at its bottom.

In this paper, we present a variation of the Spearman foot rule leading to the definition of two new measures: a point-wise (qualitative) measure and an area-wise (quantitative) measure which can be classified as non-conjoint and unweighted. 1 Point-wise and area-wise measures present analytical and geometrical properties that can be effectively used to compare different rankings and to evaluate IR experiments. Furthermore, the point-wise measure provides an intuitive and effective graphical interpretation that can be used for performing a qualitative analysis on rankings comparison. Whereas, the area-wise measure can be used for a quantitative analysis given that its normalized version offers a simple measure of correlation between rankings. Moreover, as a by-product of this approach, we also obtain an original reformulation of the Kendall rank distance computed at each rank.

Methodological Approach

Given a set of documents D = {d 1 , . . . , d i , . . . , d n }, we consider two rankings r α and r β as two permutations without repetitions of D. 2 We can use a method idx α (d i ) to extract the index of document d i within r α . In general, the problem is to find the index of a document of r α in the another ranking r β . To this purpose, we define the function F α,β (k) as:

F α,β (k) = idx β (r α (k)))(1)

This function translates the k-th document in r α and returns the index of that document in the ranking r β . For example, let

r a = [d 2 , d 1 , d 4 , d 3 ] and r b = [d 1 , d 4 , d 2 , d 3 ] be two instances of r α and r β . Then, for k = 1, F a,b (1) = idx b (r a (1)) = idx b (d 2 ) = 3.

The definition of Spearman footrule can be rewritten using Eq. 1 as:

S α,β (i) = i k=1 |F α,β (k) − k| .(2)

which is the total element-wise misplacements between the two lists r α and r β .

Point and Area Measures

The two measures we present in this paper derive from a variation of the Spearman foot rule. By removing the absolute value from the Spearman foot rule, we obtain the point-wise measure:

P α,β (i) = i k=1 (F α,β (k) − k) .(3)

As a result, we make a distinction between negative and positive misplacements: when F α,β (k) > k, we obtain a positive error because the document at rank k should have been ranked higher in r β ; when F α,β (k) < k, we obtain a negative value because we find a highly relevant document lower in the list, which means that we are recovering a misplacement occurred earlier. Ultimately, the pointwise goes to zero when the last element of the list is computed. When the pointwise measure returns a positive number at any rank i, it means that there is still some non-recovered misplacement in r b . On the other hand, every time P α,β (i) = 0 it means that the two rankings have retrieved the same elements at rank i. Compared to Spearman, the measure P α,β (i) gives us some additional information about the distance between a given ranking and the ideal one at rank i: we can tell how far we are from the ideal ranking. However, the point-wise measure does not tell how bad a ranking is before rank i.

The area-wise measure considers the area formed by the segments between two adjacent points P α,β (k −1) and P α,β (k) and the x-axis. As an approximation of the area to be measured, we use a linear interpolation between adjacent points and we define the A α,β (i) as the as a sum of all the trapezoids formed with the x-axis from rank 1 to i:

A α,β (i) = i k=1 P α,β (k − 1) + P α,β (k) 2 h (4)

where h is the height of each trapezoid, and P α,β (0) = 0 by assumption. The height h of each trapezoid can be a constant (for example h = 1), or it can be used as a tuning parameter for weighting errors differently according to the rank of the elements. The area-wise measure can be used effectively in two ways: to accumulate the information about misplacements until rank i, to compare two or more rankings given a reference ranking (for example, the ideal one). Moreover, we can also study when the same type of misplacements occur in one ranking or another (earlier or later in the ranking), for example when two adjacent relevance degrees are exchanged.

It may be convenient to normalise the value returned by the area-wise between 0 and 1. The normalisation can be done by dividing the area of a relevance list at rank i by the largest obtainable area given by the worst possible ranking, that is the ideal ranking taken in the inverse order. The normalisation of the area-wise measure is defined as:

nA α,β = A α,β A * α,β(5)

where A * α,β is the area of the worst possible ranking. The normalized area nA α,β defines the distance between β and α where nA α,β = 0 means that β and α are the same ranking and nA α,β = 1 means that they are inverse rankings one of the other. From this it is straightforward to derive the correlation coefficient as: A-corr α,β = 1 − nA α,β .

In this paper, we have introduced two new measures of distance among rankings: the point-wise and the area-wise measure. The point-wise measure was derived as a modification of the original Spearman foot rule, while the area-wise measure is built on top of the point-wise. The normalisation of the area-wise measure and the correlation coefficient derived from it -i.e. A-corr -is a measure of correlation between rankings. We have discussed some properties of these two measures in terms of qualitative analysis and quantitative analysis. For space reasons, we could not give a complete formalisation of the fact that both measures are metrics -i.e. the reflexivity, non-negativity, symmetry and triangle inequality properties hold. The area-wise measure already incorporates a parameter h that can be used to weight misplacements that happen at top ranks more than at low ranks; a possibility is to define h as the inverse of the index h(i) = 1/i. In this way, we would obtain a non-conjoint weighted distance measure. In addition, the parameter h can be used to model users search intents; for example, we could adjust the height h as a tuning parameter to represent a particular aspect of user behaviour such as the level of patience in the RBO measure [7]. Furthermore, we want to investigate the use of the point-wise curve and the A-corr measure as a full-fledged effectiveness measures. The behavior of the point-wise curve resembles the Cumulative Relative Position (CRP) [1,4] one, but it presents several key differences such as the fact that the point-wise curve does not cross the x-axis whereas the CRP one does and that CRP is defined as an effort-oriented measure and not as a correlation one.