Efficient scoring and ranking

We begin by recapping the algorithm of Figure 6.14 . For a query such as $q=$ jealous gossip, two observations are immediate:

1. The unit vector $\vec{v}(q)$ has only two non-zero components.
2. In the absence of any weighting for query terms, these non-zero components are equal - in this case, both equal 0.707.

For the purpose of ranking the documents matching this query, we are really interested in the relative (rather than absolute) scores of the documents in the collection. To this end, it suffices to compute the cosine similarity from each document unit vector $\vec{v}(d)$ to $\vec{V}(q)$ (in which all non-zero components of the query vector are set to 1), rather than to the unit vector $\vec{v}(q)$. For any two documents $d_1,d_2$

$$\vec{V}(q)\cdot \vec{v}(d_1)>\vec{V}(q)\cdot \vec{v}(d_2) \... ...row \vec{v}(q)\cdot \vec{v}(d_1)>\vec{v}(q)\cdot \vec{v}(d_2).$$ (34)

For any document $d$, the cosine similarity $\vec{V}(q)\cdot \vec{v}(d)$ is the weighted sum, over all terms in the query $q$, of the weights of those terms in $d$. This in turn can be computed by a postings intersection exactly as in the algorithm of Figure 6.14 , with line 8 altered since we take $w_{t,q}$ to be 1 so that the multiply-add in that step becomes just an addition; the result is shown in Figure 7.1 . We walk through the postings in the inverted index for the terms in $q$, accumulating the total score for each document - very much as in processing a Boolean query, except we assign a positive score to each document that appears in any of the postings being traversed. As mentioned in Section 6.3.3 we maintain an idf value for each dictionary term and a tf value for each postings entry. This scheme computes a score for every document in the postings of any of the query terms; the total number of such documents may be considerably smaller than $N$.

Figure 7.1: A faster algorithm for vector space scores.

Given these scores, the final step before presenting results to a user is to pick out the $K$ highest-scoring documents. While one could sort the complete set of scores, a better approach is to use a heap to retrieve only the top $K$ documents in order. Where $J$ is the number of documents with non-zero cosine scores, constructing such a heap can be performed in $2J$ comparison steps, following which each of the $K$ highest scoring documents can be ``read off'' the heap with $\log J$ comparison steps.