6. A method as recited in claim 1 , wherein a value of the estimated normalized discounted cumulative gain is calculated based, at least in part, on an estimated relevance rating.
6. A method as recited in claim 1 , wherein a value of the estimated normalized discounted cumulative gain is calculated based, at least in part, on an estimated relevance rating. 7. A method as recited in claim 6 , wherein the estimated relevance rating represents, for each document in a set of search results, a number of times that the document is returned in the top n results of the candidate queries associated with the user-submitted query.