Query-Dependent Ranking Using K-Nearest Neighbor

• US 20100169323A1
• Filed: 12/29/2008
• Published: 07/01/2010
• Est. Priority Date: 12/29/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Tie-Yan, Geng, Xiubo, Li, Hang
• Application Number:
  US12/344,607
• Publication Number:
  US 20100169323A1
• Time in Patent Office: Days
• US Class Current: 707/748
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 18/24147 Distances to closest patterns, e.g. nearest neighbour classification

Abstract

Described is a technology in which documents associated with a query are ranked by a ranking model that depends on the query. When a query is processed, a ranking model for the query is selected/determined based upon nearest neighbors to the query in query feature space. In one aspect, the ranking model is trained online, based on a training set obtained from a number of nearest neighbors to the query. In an alternative aspect, ranking models are trained offline using training sets; the query is used to find a most similar training set based on nearest neighbors of the query, with the ranking model that corresponds to the most similar training set being selected for ranking. In another alternative aspect, the ranking models are trained offline, with the nearest neighbor to the query determined and used to select its associated ranking model.

Claims

1. In a computing environment, a method comprising, processing a query, including finding documents for the query, determining a ranking model for the query that is dependent on the query, and using the ranking model to rank the documents.

2. The method of claim 1 wherein determining a ranking model for the query comprises training the ranking model with a learning to rank algorithm.

3. The method of claim 1 wherein determining the ranking model comprises determining at least one nearest neighbor in feature space corresponding to at least one feature of the query.

4. The method of claim 3 wherein determining a ranking model for the query comprises training a ranking model online based on a training set obtained from a number of nearest neighbors to the query.

5. The method of claim 3 wherein determining a ranking model for the query comprises training a plurality of ranking models offline with a corresponding plurality of training sets, finding a most similar training set based on nearest neighbors of the query, and selecting as the ranking model the model that corresponds to the most similar training set.

6. The method of claim 3 wherein determining a ranking model for the query comprises training a plurality of ranking models offline with a corresponding plurality of training sets, finding a nearest neighbor to the query, and selecting as the ranking model the model that is associated with a training set corresponding to a nearest neighbor of the query.

7. The method of claim 3 further comprising finding the at least one feature of the query, including finding a top number of documents associated with the query, and extracting at least one feature from the top number of the documents.

8. The method of claim 7 wherein one feature of the query comprises a mean of the feature values of the top number of documents.

9. In a computing environment, a system comprising, a featurizer that extracts features of a new query, and a selection mechanism that selects a ranking model for the new query that is dependent on the query, the ranking model used to rank documents associated with the query.

10. The system of claim 9 further comprising a trainer that trains the ranking model from training queries using a learning to rank algorithm.

11. The system of claim 9 wherein the featurizer is coupled to a reference model that finds a top number of documents associated with the new query, and extracts features from the top number of documents.

12. The system of claim 11 wherein the reference model comprises a BM25-based mechanism.

13. The system of claim 9 wherein the selection mechanism is coupled to an online training mechanism that trains the ranking model online based on a training set obtained from a number of nearest neighbors to the query.

14. The system of claim 9 wherein the selection mechanism is coupled to an offline training mechanism that trains a plurality of ranking models offline with a corresponding plurality of training sets, the selection mechanism finding a most similar training set based on nearest neighbors of the query, and selecting the ranking model based upon the most similar training set.

15. The system of claim 9 wherein the selection mechanism is coupled to an offline training mechanism that trains a plurality of ranking models offline with a corresponding plurality of training sets, the selection mechanism finding a nearest neighbor to the query, and selecting the ranking model based upon the nearest neighbor of the query.

16. One or more computer-readable media having computer-executable instructions, which when executed perform steps, comprising, processing a query, including finding documents for the query, selecting a ranking model for the query that is dependent on the query, including by finding at least one nearest neighbor of the query in query feature space, and using the ranking model to rank the documents.

17. The one or more computer-readable media of claim 16 wherein selecting the ranking model comprises training a ranking model online based on a training set obtained from a number of nearest neighbors to the query.

18. The one or more computer-readable media of claim 16 wherein selecting the ranking model comprises training a plurality of ranking models offline with a corresponding plurality of training sets, finding a most similar training set based on nearest neighbors of the query, and selecting as the ranking model the model that corresponds to the most similar training set.

19. The one or more computer-readable media of claim 16 wherein selecting the ranking model comprises training a plurality of ranking models offline with a corresponding plurality of training sets, finding a nearest neighbor to the query, and selecting as the ranking model the model that is associated with a training set corresponding to a nearest neighbor of the query.

20. The one or more computer-readable media of claim 16 having further computer-executable instructions comprising featurizing the query, including by finding a top number of documents associated with the query, and extracts featuring for the query based upon information in the top number of documents.