SYSTEM FOR FINDING QUERIES AIMING AT TAIL URLs

• US 20100179929A1
• Filed: 01/09/2009
• Published: 07/15/2010
• Est. Priority Date: 01/09/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Liu, Fang, Dohzen, Tiffany Kumi, Stewart, Ryan Frederick, Nair, Vijay Ravindran, Wang, Yi-Min, Yin, Xiaoxin, Wang, Junhua
• Granted Patent: US 8,145,622 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Systems and methodologies for improved query classification and processing are provided herein. As described herein, a query prediction model can be constructed from a set of training data (e.g., diagnostic data obtained from an automatic diagnostic system and/or other suitable data) using a machine learning-based technique. Subsequently upon receiving a query, a set of features corresponding to the query, such as the length and/or frequency of the query, unigram probabilities of respective words and/or groups of words in the query, presence of pre-designated words or phrases in the query, or the like, can be generated. The generated features can then be analyzed in combination with the query prediction model to classify the query by predicting whether the query is aimed at a head Uniform Resource Locator (URL) or a tail URL. Based on this prediction, an appropriate index or combination of indexes can be assigned to answer the query.

Claims

1. A system for classifying a query in relation to one or more indexes to which the query is to be directed, comprising:

one or more computer memories that store data relating to at least one index; and

at least one processor coupled to the one or more computer memories, the at least one processor configured to act as;

a feature generation component that generates one or more features corresponding to a query;

a model building component that builds a prediction model for respective queries by utilizing a machine learning algorithm and an associated set of training data; and

a predicting component that analyzes the one or more features corresponding to the query and the prediction model to predict whether the query is directed to a resource pre-designated as a commonly queried resource or a resource pre-designated as an uncommonly queried resource.

2. The system of claim 1, wherein the one or more features corresponding to the query generated by the feature generation component comprise frequency with which the query is received.

3. The system of claim 1, wherein the one or more features corresponding to the query generated by the feature generation component comprise length of the query in one or more of characters or words.

4. The system of claim 1, wherein the one or more features corresponding to the query generated by the feature generation component comprise unigram probabilities of respective words or phrases in the query based on a frequency with which the respective words or phrases in the query appear in at least one of a set of indexed resources or a set of previously received queries.

5. The system of claim 4, wherein the feature generation component computes at least one representative unigram probability for the query as a logarithm of one or more of a maximum unigram probability, a minimum unigram probability, or an average unigram probability generated for respective words or phrases in the query.

6. The system of claim 1, wherein the one or more features corresponding to the query generated by the feature generation component comprise point-wise mutual information corresponding to respective probabilities that respective groups of consecutive words in the query appear together in indexed resources.

7. The system of claim 6, wherein the feature generation component computes at least one representative set of maximum, minimum, or average point-wise mutual information inferred from probabilities that respective groups of consecutive words in the query appear together in indexed resources.

8. The system of claim 1, wherein the one or more features corresponding to the query generated by the feature generation component comprise information relating to presence of one or more words in the query that are defined as associated with resources pre-designated as uncommonly queried resources.

9. The system of claim 1, wherein the at least one processor is further configured to act as a positive/negative query collection component that collects positive query training data comprising respective queries aimed at resources pre-designated as uncommonly queried resources and negative query training data comprising respective queries aimed at resources pre-designated as commonly queried resources.

10. The system of claim 9, wherein the feature generation component generates one or more features of the respective queries included in the positive query training data and the negative query training data and the model building component builds the query prediction model by utilizing the one or more features of the respective queries included in the positive query training data and the negative query training data and the resources to which the respective queries in the positive query training data and the negative query training data are directed as at least a portion of the training data.

11. The system of claim 1, wherein:

the at least one index comprises a first index having an associated first speed and first capacity and a second index having an associated second speed that is slower than the first speed and a second capacity that is larger than the first capacity; and

the predicting component associates queries predicted to be directed to resources pre-designated as commonly queried resources with the first index and associates queries predicted to be directed to resources pre-designated as uncommonly queried resources with the first index and the second index.

12. The system of claim 1, wherein the predicting component applies one or more of a first priority level or a first optimization level to queries predicted to be directed to resources pre-designated as commonly queried resources and applies one or more of a second priority level or a second optimization level to queries predicted to be directed to resources pre-designated as uncommonly queried resources, wherein the second priority level and the second optimization level are respectively disparate from the first priority level and the second optimization level.

13. A method of classifying and answering a query, comprising:

employing one or more processors to perform the classifying and answering, the classifying and answering comprising;

creating a prediction model for respective queries based on a set of diagnostic data using one or more machine learning algorithms, the set of diagnostic data comprising respective pairs of a query and an identity of an indexed resource to which the query is directed;

identifying a query;

generating one or more features corresponding to the query; and

predicting whether the query is directed to a commonly queried resource or an uncommonly queried resource by analyzing the one or more features corresponding to the query and the prediction model.

14. The method of claim 13, wherein the generating comprises determining one or more features relating to frequency with which the query is received.

15. The method of claim 13, wherein the generating comprises determining one or more features relating to a number of characters in the query or a number of words in the query.

16. The method of claim 13, wherein the generating comprises determining one or more features relating to at least one of frequency with which respective words or phrases in the query appear in respective indexed resources or probability that respective groups of words in the query appear together in respective indexed resources.

17. The method of claim 13, wherein the generating comprises determining one or more features relating to presence of predetermined action words in the query that are designated as likely to be aimed at uncommonly queried resources.

18. The method of claim 13, wherein the creating a prediction model comprises collecting training data comprising positive query data comprising respective queries aimed at uncommonly queried resources and negative query data comprising respective queries aimed at commonly queried resources.

19. The method of claim 18, wherein the creating a prediction model further comprises:

generating one or more features of the respective queries included in the positive query data and the negative query data; and

utilizing at least one of the one or more features of the respective queries included in the positive query data and the negative query data or identities of resources to which the respective queries in the positive query data and the negative query data are aimed as training data in creating the prediction model.

20. A machine-readable medium having stored thereon instructions which, when executed by a machine, cause the machine to act as a query processing system comprising:

means for obtaining a set of positive search data from an automatic diagnostic system comprising one or more queries aimed at Uniform Resource Locators (URLs) indexed by a large search index;

means for obtaining a set of negative search data from the automatic diagnostic system comprising one or more queries aimed at respective URLs indexed by a small search index;

means for constructing a prediction model from the positive search data and the negative search data using a machine learning algorithm;

means for receiving a newly-submitted query;

means for obtaining one or more features of the newly-submitted query;

means for predicting whether the newly-submitted query is aimed at a URL indexed by the small index or a URL indexed by the large index based on the features of the newly-submitted query and the prediction model; and

means for answering the newly-submitted query using the small index upon predicting that the newly-submitted query aims at a URL indexed by the small index or using the small index and the large index upon predicting that the newly-submitted query aims at a URL indexed by the large index.