System for finding queries aiming at tail URLs

• US 8,145,622 B2
• Filed: 01/09/2009
• Issued: 03/27/2012
• Est. Priority Date: 01/09/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Junhua, Dohzen, Tiffany Kumi, Wang, Yi-Min, Yin, Xiaoxin, Nair, Vijay Ravindran, Stewart, Ryan Frederick, Liu, Fang
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US12/351,013
• Publication Number:
  US 20100179929A1
• Time in Patent Office: 1,173 Days
• Field of Search: 707/104, 707/713, 707/709, 707/705, 707/5, 707/2, 707/708, 707/71, 706/14, 706/12
• US Class Current: 707/713
• 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 being configured to act as;

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

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

a predicting component that;

analyzes the one or more features corresponding to the query and the prediction model, and

predicts, based at least on the analyzing, 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 comprise frequency with which the query is received.

3. The system of claim 1, wherein the one or more features corresponding to the query 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 comprise unigram probabilities of respective words or phrases in the query, the unigram probabilities being computed based on at least 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 at least one 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 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 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 queries aimed at resources pre-designated as uncommonly queried resources and negative query training data comprising queries aimed at resources pre-designated as commonly queried resources.

10. The system of claim 9, wherein:

the feature generation component further generates at least one feature corresponding to each of the queries included in the positive query training data and the negative query training data; and

the model building component further builds the query prediction model by utilizing the at least one feature and the resources to which the queries 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 further 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 second index.

12. The system of claim 1, wherein the predicting component further 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, the second priority level and the second optimization level being respectively disparate from the first priority level and the first 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 one query and an identity of an indexed resource to which the one query is directed;

identifying the 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 the one or more features relating to frequency with which the query is received.

15. The method of claim 13, wherein the generating comprises determining the 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 the 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 the respective indexed resources.

17. The method of claim 13, wherein the generating comprises determining the 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 including queries aimed at uncommonly queried resources, and negative query data including queries aimed at commonly queried resources.

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

generating at least one feature corresponding to each of the queries included in the positive query data and the negative query data; and

utilizing at least one of the at least one feature of the queries or identities of resources to which the queries are aimed as the training data in creating the prediction model.

20. A machine-readable storage medium having stored thereon instructions that, when executed by a machine, perform acts comprising:

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

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

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

receiving a newly-submitted query;

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

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

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 large index upon predicting that the newly-submitted query aims at a URL indexed by the large index.