AUTOMATIC QUERY SUGGESTION GENERATION USING SUB-QUERIES

• US 20110258212A1
• Filed: 04/14/2010
• Published: 10/20/2011
• Est. Priority Date: 04/14/2010
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: WAN, HOWARD SHI KIN, ZHANG, DONGHUI, LU, JIANPING
• Application Number:
  US12/760,128
• Publication Number:
  US 20110258212A1
• Time in Patent Office: Days
• US Class Current: 707/760
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Query suggestions can be generated by identifying desirable sub-queries. Search engine data can be accumulated to determine usage characteristics for various queries. Potential sub-queries can be generated and ranked based on the usage data. After ranking potential sub-queries, the rankings can be used to select sub-queries when a search request is received. The selected sub-queries can be used directly as query suggestions, or the sub-queries can be used as input for another query suggestion engine.

Claims

1. One or more computer readable media containing computer executable instructions that, when executed, provide a method for generating query suggestions, comprising:

obtaining a query logfile;

identifying queries contained in the query logfile that have at least 4 query elements;

determining sub-queries for each identified query;

matching the determined sub-queries to queries in the query logfile;

calculating a ranking for each matched sub-query, the ranking being based on a number of distinct users, page view data, a number of query elements in the sub-query, and a number of parent queries for the sub-query;

receiving a search query;

determining search sub-queries for the received search query, at least one of the search sub-queries corresponding to a matched sub-query having a calculated ranking;

selecting one or more search sub-queries based on the corresponding calculated ranking of the selected one or more search sub-queries; and

providing one or more suggested queries based on the selected one or more search sub-queries.

2. The one or more computer readable media of claim 1, wherein determining sub-queries for each identified query comprises determining n-grams having for each identified query.

3. The one or more computer readable media of claim 1, wherein determining sub-queries for each identified query comprises determining position independent sub-queries for each identified query, each position independent sub-query having fewer query elements than the corresponding identified query.

4. The one or more computer readable media of claim 1, wherein said identifying queries contained in the query logfile, said determining sub-queries for each identified query, said matching the determined sub-queries, and said calculating a ranking for each matched sub-query are performed automatically.

5. The one or more computer readable media of claim 1, further comprising filtering the query logfile to exclude one or more queries, wherein identifying queries contained in the query logfile comprises identifying queries based on the filtered queries.

6. The one or more computer readable media of claim 1, wherein determining sub-queries for each identified query comprises determining sub-queries that have a threshold number of query terms or less.

7. The one or more computer readable media of claim 1, wherein providing one or more suggested queries based on the selected one or more search sub-queries comprises using the selected one or more search sub-queries as input for a query suggestion engine and providing at least one query generated by the query suggestion engine.

8. The one or more computer readable media of claim 1, wherein the identified queries contain from 4 to about 60 query elements.

9. A method for generating query suggestions for queries in a character-based written language, comprising:

obtaining a query logfile containing queries having query elements corresponding to characters in a character-based written language;

identifying queries contained in the query logfile that have at least 4 query elements;

determining sub-queries for each identified query;

matching the determined sub-queries to queries in the query logfile;

calculating a ranking for each matched sub-query, the ranking being based on a number of distinct users, page view data, a number of query elements in the sub-query, and a number of parent queries for the sub-query;

receiving a search query;

determining search sub-queries for the received search query, at least one of the search sub-queries corresponding to a matched sub-query having a calculated ranking;

selecting one or more search sub-queries based on the corresponding calculated ranking of the selected one or more search sub-queries; and

providing one or more suggested queries based on the selected one or more search sub-queries.

10. The method of claim 9, wherein the character-based written language is Chinese, Japanese, or Korean.

11. The method of claim 9, wherein determining sub-queries for each identified query comprises determining n-grams having for each identified query.

12. The method of claim 9, wherein determining sub-queries for each identified query comprises determining position independent sub-queries for each identified query, each position independent sub-query having fewer query elements than the corresponding identified query.

13. The method of claim 9, wherein the identified queries contain from 4 to about 60 query elements.

14. The method of claim 9, wherein calculating a ranking for each matched sub-query comprises:

calculating a number of parent queries for each sub-query;

calculating a frequency for each sub-query based on a number of distinct users and page view information;

calculating one or more normalized weighted frequency values for each sub-query based on the number of query elements in the sub-query, the number of query elements in a parent query, a number of queries in the query logfile, and a number of parent queries for the sub-query, wherein a number of normalized weighted frequency values calculated for a sub-query corresponds to the number of parent queries for the sub-query; and

calculating an average normalized weighted frequency value for a sub-query based on the one or more normalized weighted frequency values for the sub-query and the number of parent queries for the sub-query.

15. One or more computer readable media containing computer executable instructions that, when executed, provide a method for automatically generating a sub-query ranking list, comprising:

obtaining a query logfile;

identifying queries contained in the query logfile that have at least 4 query elements;

determining sub-queries for each identified query;

matching the determined sub-queries to queries in the query logfile;

calculating a ranking for each matched sub-query, the calculation comprising;

calculating a number of parent queries for each sub-query;

calculating a frequency for each sub-query based on a number of distinct users and page view information;

calculating one or more normalized weighted frequency values for each sub-query based on the number of query elements in the sub-query, the number of query elements in a parent query, a number of queries in the query logfile, and a number of parent queries for the sub-query, wherein a number of normalized weighted frequency values calculated for a sub-query corresponds to the number of parent queries for the sub-query; and

calculating an average normalized weighted frequency value for a sub-query based on the one or more normalized weighted frequency values for the sub-query and the number of parent queries for the sub-query;

and

generating a ranking list of sub-queries based on the average normalized weighted frequency values for the sub-queries.

16. The one or more computer readable media of claim 15, wherein the average normalized weighted frequency value is further based on the number of query terms in the sub-query.

17. The one or more computer readable media of claim 15, wherein the method further comprises providing the generated ranking list to a query suggestion engine.

18. The one or more computer readable media of claim 15, wherein the method further comprises:

receiving a search query;

determining search sub-queries for the received search query, at least one of the search sub-queries corresponding to a sub-query in the ranking list;

selecting one or more search sub-queries based on the corresponding calculated ranking of the selected one or more search sub-queries; and

providing one or more suggested queries based on the selected one or more search sub-queries.

19. The one or more computer readable media of claim 15, wherein a query element corresponds to a character of a character-based written language.

20. The one or more computer readable media of claim 15, further comprising filtering the query logfile to exclude one or more queries, wherein identifying queries contained in the query logfile comprises identifying queries based on the filtered queries.