Provided is a method and computer program product for determining a document relevance function for estimating a relevance score of a document in a database with respect to a query. For each of a plurality of test queries, a respective set of result documents is collected. For each test query, a subset of the documents in the respective result set is selected, and a set of training relevance scores is assigned to documents in the subset. In one embodiment, at least some of the training relevance scores are assigned by human subjects who determine individual relevance scores for submitted documents with respect to the corresponding queries. Finally, a relevance function is determined based on the plurality of test queries, the subsets of documents, and the sets of training relevance scores.