Query expansion using query logs

• US 20040249808A1
• Filed: 06/06/2003
• Published: 12/09/2004
• Est. Priority Date: 06/06/2003
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Azzam, Saliha, Calcagno, Michael V., Humphreys, Kevin W.
• Application Number:
  US10/455,995
• Publication Number:
  US 20040249808A1
• Time in Patent Office: Days
• US Class Current: 707/4
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

In a method of processing an input query, an input query is received and a related query is selected from a query log. Next, the selected query is provided to a query processing system in place of the original input query. The present invention is also directed to a query modification system that is configured to perform the above-described method.

Claims

1. A method of processing an input query comprising steps of:

a) receiving an input query;

b) selecting a query from a query log;

c) replacing the input query with the selected query from the query log; and

d) providing the selected query to a query processing system.

2. The method of claim 1, including grouping related or similar queries of the query log into clusters prior to the selecting step b).

3. The method of claim 2, wherein the grouping step includes comparing the queries at a string level, comparing the queries after lemmatization, comparing semantic types of the queries, or comparing abstract semantic representations of the queries.

4. The method of claim 2, wherein each of the clusters of queries is labeled with a representative query that is representative of the queries contained in the cluster;

and the query selected in step b) is one of the representative queries of the clusters.

5. The method of claim 4, wherein the selecting step b) includes:

comparing significant terms of each cluster'"'"'s representative query to significant terms of the input query;

selecting at least one candidate cluster whose representative query includes all of the significant terms of the input query;

wherein the selected query is the representative query of one of the candidate clusters.

6. The method of claim 4 including ranking the clusters based upon a weight given to their corresponding representative queries.

7. The method of claim 6, wherein representative queries of the clusters representing more complete questions are given more weight than those representing less complete questions.

8. The method of claim 6, wherein clusters generated from more recent query logs are given more weight than clusters generated earlier.

9. The method of claim 6, wherein the representative query is chosen in the selecting step b) based upon its rank.

10. The method of claim 1, wherein the selecting step b) includes comparing significant terms of the queries of the query log to significant terms of the input query.

11. The method of claim 2, wherein the grouping step includes:

comparing significant terms of the queries of the query log;

grouping similar queries into the same cluster;

selecting one of the queries of each cluster as a representative query for the cluster.

12. The method of claim 1 including ranking the queries in the query log based upon a weight given to each processed query, wherein the selected query is chosen in the selecting step b) based upon its rank.

13. The method of claim 12, wherein queries having a predetermined characteristic are given more weight than those lacking the predetermined characteristic.

14. The method of claim 13, wherein the predetermined characteristic is a frequency at which the query or an abstract representation of the query occurs, a completeness with which the query represents a question, or a recency of the query log from which the query was taken.

15. The method of claim 11 including ranking the representative queries of each cluster based upon a weight given to each, wherein the query selected in the selecting step b) is the representative query having the highest rank.

16. The method of claim 15, wherein queries having a higher frequency of occurrence in the cluster are given more weight than those having a lower frequency of occurrence in the cluster.

17. The method of claim 15, wherein queries of the clusters representing more complete questions are given more weight in the cluster than those representing less complete questions.

18. The method of claim 15, wherein the selected query is chosen in the selecting step b) based upon its rank within the candidate cluster and an inclusiveness of the significant terms of the input query.

19. A method of processing an input query comprising:

a) grouping related or similar queries from a query log into clusters;

b) receiving an input query;

c) associating one or more clusters with the input query;

d) selecting a query from an associated cluster or a representative query corresponding to the associated cluster;

e) replacing the input query with the selected query; and

f) providing the selected query to a query processing system.

20. The method of claim 19, wherein the grouping step a) includes comparing the queries at a string level, comparing the queries after lemmatization, comparing semantic types of the queries, or comparing abstract semantic representations of the queries.

21. The method of claim 19, wherein the associating step c) includes:

comparing significant terms of the representative queries to significant terms of the input query; and

selecting one or more candidate clusters each having a representative query that includes all of the significant terms of the input query;

wherein the selected query is one of the representative queries of the candidate clusters.

22. The method of claim 21 including ranking the candidate clusters based upon a weight given to their corresponding representative query, wherein the representative query is chosen in the selecting step d) based upon its rank.

23. The method of claim 22, wherein representative queries of the candidate clusters representing more complete questions are given more weight than those representing less complete questions.

24. The method of claim 22, wherein representative queries corresponding to candidate clusters containing more recent queries are given more weight than those corresponding to candidate clusters containing less recent queries.

25. The method of claim 19, wherein the associating step c) includes:

comparing significant terms of the queries contained in each cluster to significant terms of the input query; and

selecting one or more candidate clusters for association with the input query, each candidate cluster including all of the significant terms of the input query;

wherein the selected query is contained in one of the candidate clusters.

26. The method of claim 25 including ranking the queries in each of the candidate clusters based upon a weight given to each query of the candidate clusters.

27. The method of claim 26, wherein queries having a predetermined characteristic are given more weight than those lacking the predetermined characteristic.

28. The method of claim 27, wherein the predetermined characteristic is a frequency at which the query or a logical representation of the query occurs in the candidate cluster, a completeness at which the query represents a question, or how recent the query was generated.

29. The method of claim 26, wherein queries having a higher frequency of occurrence in the candidate cluster are given more weight than those having a lower frequency of occurrence in the candidate cluster.

30. The method of claim 26, wherein candidate clusters with more complete questions are given more weight than those with less complete questions.

31. The method of claim 25, wherein the selected query is chosen in the selecting step b) based upon its cluster'"'"'s rank and an inclusiveness of the significant terms of the input query.

32. A query modification system for providing a query to a query processing system in response to an input query, the system comprising:

a query organizer configured to organize queries from a query log into clusters of similar or related queries-, each cluster having a representative query that is representative of the queries contained in the cluster;

a query log manager configured to compare the representative queries to the input query and select candidate representative queries or clusters that are closely related to the input query;

a cluster ranking component configured to rank the candidate clusters or representative queries based upon their similarity to the input query; and

a query selecting component configured to select and provide one of the representative queries of the candidate clusters to the query processing system based on its rank.

33. A method of generating an information extraction template from a query processing system comprising steps of:

a) selecting multiple queries from a query log that relate to an input query;

b) generating a list of answer types and descriptions, each of which correspond to one of the selected queries; and

c) generating an information extraction template containing answer fields and descriptions, each answer field corresponding to one of the answer types in the list.

34. The method of claim 33 including a step b)1) of removing duplicate answer types from the list.

35. The method of claim 33 including a step d) of extracting answers from search results that have answer types that correspond to the answer fields of the template.