1. A method in a computer system for providing improved search results in response to a user query, the method comprising: obtaining a set of ranked query item pairs, each query item pair corresponding to a query and a hit document, each query item further corresponding to a set of feature vectors including a set of features and corresponding feature weights; executing a series of query relaxation operations, each query relaxation operation extracting one of the set of feature vectors for an item pair and calculating a relevancy score using the extracted feature vector and a learned ranking function that is unique for that query relaxation operation; and generating a hit list for the user query to be displayed to the user that contains hits from the executed query relaxation operations.