Term suggestion for multi-sense query

• US 7,428,529 B2
• Filed: 04/15/2004
• Issued: 09/23/2008
• Est. Priority Date: 04/15/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Najm, Tarek, Li, Li, Zhang, Benyu, Li, Ying, Zeng, Hua-Jun
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): Le; Jessica N
• Application Number:
  US10/825,894
• Publication Number:
  US 20050234879A1
• Time in Patent Office: 1,622 Days
• Field of Search: 707/3, 707 4- 7, 707/102, 395/600, 704/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

Systems and methods for related term suggestion are described. In one aspect, term clusters are generated as a function of calculated similarity of term vectors. Each term vector having been generated from search results associated with a set of high frequency of occurrence (FOO) historical queries previously submitted to a search engine. Responsive to receiving a term/phrase from an entity, the term/phrase is evaluated in view of terms/phrases in the term clusters to identify one or more related term suggestions.

Claims

1. A computer-implemented method for related term suggestion, the method comprising:

mining search results via a multi-sense query, wherein the multi-sense query comprises;

determining terms/phrases semantically related to submitted terms/phrases, wherein semantic relationships are discovered by mining a context of the terms/phrases to determine meaning;

configuring a threshold frequency of occurrence (FOO) value;

assigning historical queries to high FOO or low FOO based on the configured threshold value;

generating term vectors from the search results associated with a set of high FOO historical queries previously submitted to a search engine; and

generating term clusters as a function of calculated similarity of term vectors, wherein calculated similarity, sim(q_j, q_k), is determined as follows;

$\mathrm{sim}<br><br>\left(q_j,q_k\right)=\underset{i=1}{\overset{d}{\sum <br><br>}}<br><br><br><br>w_{\mathrm{ij}}·<br><br>w_{\mathrm{ik}};<br><br>$

wherein d represents vector dimension, q represents a query, k is a dimension index, and wherein weight w for the i^th vector'"'"'s j^th term is calculated as follows;

w_ij=TF_ij×

log(N/DF_j); and

wherein TF_ij represents term frequency, N is a total number of query terms, and DF_j is a number of extracted feature records that contain the i^th vector'"'"'s j^th term;

responsive to receiving a term/phrase from an entity, evaluating the term/phrase via the multi-sense query in view of terms/phrases in the term clusters to identify one or more related term suggestions, wherein the identifying is based on a combination of FOO and a confidence value; and

returning at least one suggested term list ordered by the combination of FOO and confidence value, wherein multiple suggested term lists are generated when the term/phrase matches terms in more than one term cluster.

2. The method of claim 1, and wherein the entity is a computer-program application or an end-user.

3. The method of claim 1, further comprising:

collecting historic query from a query log; and

determining ones of the historic query terms with the high FOO.

4. The method of claim 1, further comprising before creating the term clusters:

reducing dimensionality of the term vectors; and

normalizing the term vectors.

5. The method of claim 1, wherein evaluating further comprises:

identifying a match between die term/phrase and term(s)/phrase(s) from one or more term clusters; and

responsive to identifying, generating related term suggestion(s) comprising the term(s)/phase(s).

6. The method of claim 5, wherein the related term suggestion(s) further comprise for each term/phrase of the term(s)/phrase(s), a frequency of occurrence value indicating a number of times the term/phrase occurs in a set of mined historical queries.

7. The method as recited in claim 1, wherein generating the term clusters further comprises:

sending respective ones of the high FOO historical queries to the search engine to obtain the search results;

extracting features from at least a subset of search results corresponding to the respective ones;

producing the term vectors from the features as a function of the term and inverted document frequencies.

8. The method of claim 7, and wherein the features comprise a title, description, and/or context for the respective ones of the high FOO historical query terms.

9. The method of claim 7, and wherein the respective ones comprise top ranked ones of the search results.

10. The method of claim 1, wherein the term clusters are a first set of term clusters, and wherein the method further comprises:

determining that there is no match between the term/phrase and the terms/phrases; and

responsive to the determining;

making a second set of term clusters from calculated similarity of term vectors, each term vector being generated from search results associated with a set of low FOO historical queries previously submitted to the search engine; and

evaluating the term/phrase in view of terms/phrases of the second set of term clusters to identify one or more related term suggestions.

11. The method of claim 10, wherein making further comprises:

identifying the low FOO historical queries from historical queries mined from the query log;

sending respective ones of at least a subset of the low FOO historical queries to the search engine to obtain search results;

extracting features from at least a subset of search results

producing the term vectors from the features as a function of the term and inverted term frequencies.

12. The method of claim 11, and further comprising after clustering:

determining that there is no match between the term/phrase and term(s)/phrase(s) from the first set of term clusters, the first set being based on the high FOO historical queries; and

responsive to the determining, identifying a match between the term/phrase and term(s)/phrase(s) from one or more of the second set of term clusters, the second set being based on the low FOO historical queries; and

responsive to identifying, generating related term suggestion(s) comprising the term(s)/phrase(s).

13. A tangible computer-readable data storage medium comprising computer-executable instructions for executing a method, the method comprising:

mining search results via a multi-sense query, wherein the multi-sense query comprises;

determining terms/phrases semantically related to submitted terms/phrases, wherein semantic relationships are discovered by mining a context of the terms/phrases to determine meaning;

configuring a threshold frequency of occurrence (FOO) value;

assigning historical queries to high FOO or low FOO based on the configured threshold value;

generating term vectors from the search results associated with a set of high FOO historical queries previously submitted to a search engine; and

generating term clusters as a function of calculated similarity of term vectors, wherein calculated similarity, sim(q_j, q_k), is determined as follows;

$\mathrm{sim}<br><br>\left(q_j,q_k\right)=\underset{i=1}{\overset{d}{\sum <br><br>}}<br><br><br><br>w_{\mathrm{ij}}·<br><br>w_{\mathrm{ik}};<br><br>$

wherein d represents vector dimension, q represents a query, k is a dimension index, and wherein weight w for the i^th vector'"'"'s j^th term is calculated as follows;

w_ij=TF_ij×

log(N/DF_j); and

wherein TF_j represents term frequency, N is a total number of query terms, and DF_j is a number of extracted feature records that contain the i^th vector'"'"'s j^th term;

responsive to receiving a term/phrase from an entity, evaluating the term/phrase via the multi-sense query in view of terms/phrases in the term clusters to identify one or more related term suggestions, wherein the identifying is based on a combination of FOO and a confidence value; and

returning at least one suggested term list ordered by the combination of FOO and confidence value, wherein multiple suggested term lists are generated when the term/phrase matches terms in more than one term cluster.

14. The computer-readable data storage medium of claim 13, and wherein the entity is a computer-program application and/or an end-user.

15. The computer-readable data storage medium of claim 13, wherein the method further comprises:

collecting historic query from a query log; and

determining ones of the historic query terms with the high FOO.

16. The computer-readable data storage medium of claim 13, wherein the method further comprises:

reducing dimensionality of the term vectors; and

normalizing the term vectors,

wherein the reducing and normalizing are executed before creating the term clusters.

17. The computer-readable data storage medium of claim 13, wherein evaluating the term/phrase via the multi-sense query comprises:

identifying a match between the term/phrase and term(s)/phrase(s) from one or more term clusters; and

responsive to identifying, generating related term suggestion(s) comprising the term(s)/phrase(s).

18. The computer-readable data storage medium of claim 17, wherein the related term suggestion(s) comprise for each term/phrase of the term(s)/phrase(s), a frequency of occurrence value indicating a number of times the term/phrase occurs in a set of mined historical queries.

19. The computer-readable data storage medium of claim 13, wherein generating the term clusters further comprises:

sending respective ones of the high FOO historical queries to the search engine to obtain the search results;

extracting features from at least a subset of search results corresponding to the respective ones;

producing the term vectors from the features as a function of the term and inverted document frequencies.

20. The computer-readable data storage medium of claim 19, and wherein the features comprise a title, description, and/or context for the respective ones of the high FOO historical query terms.

21. The computer-readable data storage medium of claim 19, and wherein the respective ones comprise top ranked ones of the search results.

22. The computer-readable data storage medium of claim 13, wherein the term clusters are a first set of term clusters, and wherein the method further comprises:

determining that there is no match between the term/phrase and the terms/phrases; and

responsive to determining that there is no match between the term/phrase and the terms/phrases;

making a second set of term clusters from calculated similarity of term vectors, each term vector being generated from search results associated with a set of low FOO historical queries previously submitted to the search engine; and

evaluating the term/phrase in view of terms/phrases of the second set of term clusters to identify one or more related term suggestions.

23. The computer-readable data storage medium of claim 22, wherein making a second set of term clusters comprises:

identifying the low FOO historical queries from historical queries mined from the query log;

sending respective ones of at least a subset of the low FOO historical queries to the search engine to obtain search results;

extracting features from at least a subset of search results

producing the term vectors from the features as a function of the term and inverted term frequencies.

24. The computer-readable data storage medium of claim 23, wherein the method further comprising:

after clustering;

determining that there is no match between the term/phrase and term(s)/phrase(s) from the first set of term clusters, the first set being based on the high FOO historical queries; and

responsive to the determining, identifying a match between the term/phrase and term(s)/phrase(s) from one or more of the second set of term clusters, the second set being based on the low FOO historical queries; and

responsive to identifying, generating related term suggestion(s) comprising the term(s)/phrase(s).

25. A computing device comprising:

a processor; and

a memory couple to the processor, the memory comprising computer-program instructions executable by the processor for;

mining search results via a multi-sense query, wherein the multi-sense query comprises;

determining terms/phrases semantically related to submitted terms/phrases, wherein semantic relationships are discovered by mining a context of the terms/phrases to determine meaning;

configuring a threshold frequency of occurrence (FOO) value;

assigning historical queries to high FOO or low FOO based on the configured threshold value;

generating term vectors from the search results associated with a set of high FOO historical queries previously submitted to a search engine; and

generating term clusters as a function of calculated similarity of term vectors, wherein calculated similarity, sim(q_i, q_k), is determined as follows;

$\mathrm{sim}<br><br>\left(q_j,q_k\right)=\underset{i=1}{\overset{d}{\sum <br><br>}}<br><br><br><br>w_{\mathrm{ij}}·<br><br>w_{\mathrm{ik}};<br><br>$

wherein d represents vector dimension, q represents a query, k is a dimension index, and wherein weight w for the i^th vector'"'"'s j^th term is calculated as follows;

w_ij=TF_ij×

log(N/DF_j); and

wherein TF_j represents term frequency, N is a total number of query terms, and DF_j is a number of extracted feature records that contain the i^th vector'"'"'s j^th term;

responsive to receiving a term/phrase from an entity, evaluating the term/phrase via the multi-sense query in view of terms/phrases in the term clusters to identify one or more related term suggestions, wherein the identifying is based on a combination of FOO and a confidence value; and

returning at least one suggested term list ordered by the combination of FOO and confidence value, wherein multiple suggested term lists are generated when the term/phrase matches terms in more than one term cluster.

26. The computing device of claim 25, wherein the entity is a computer-program application or an end-user.

27. The computer device of claim 25, further comprising computer-program instructions executable by the processor for:

collecting historic query from a query log; and

determining ones of the historic query terms with the high FOO.

28. The computing device of claim 25, before creating the term clusters, further comprising computer-program instructions executable by the processor for:

reducing dimensionality of the term vectors; and

normalizing the term vectors.

29. The computing device of claim 25, wherein evaluating comprises computer-program instructions executable by the processor for:

identifying a match between the term/phrase and term(s)/phrase(s) from one or more term clusters; and

responsive to identifying, generating related term suggestion(s) comprising the term(s)/phrase(s).

30. The computing device of claim 29, wherein the related term suggestion(s) further comprise for each term/phrase of the term(s)/phrase(s), a frequency of occurrence value indicating a number of times the term/phrase occurs in a set of mined historical queries.

31. The method of claim 25, wherein generating the term clusters further comprises computer-program instructions executable by the processor for:

sending respective ones of the high FOO historical queries to the search engine to obtain the search results;

extracting features from at least a subset of search results corresponding to the respective ones;

producing the term vectors from the features as a function of the term and inverted document frequencies.

32. The computing device of claim 31, and wherein the features comprise a title, description, and/or context for the respective ones of the high FOO historical query terms.

33. The computing device of claim 31, and wherein the respective ones comprise top ranked ones of the search results.

34. The computing device of claim 25, wherein the term clusters are a first set of term clusters, and wherein the computer-executable instructions further comprise instructions for:

determining that there is no match between the term/phrase and the terms/phrases; and

responsive to the determining;

making a second set of term clusters from calculated similarity of term vectors, each term vector being generated from search results associated with a set of low FOO historical queries previously submitted to the search engine; and

evaluating the term/phrase in view of terms/phrases of the second set of term clusters to identify one or more related term suggestions.

35. The method of claim 34, wherein making a second set of term clusters comprises computer-executable instructions for:

identifying the low FOO historical queries from historical queries mined from the query log;

sending respective ones of at least a subset of the low FOO historical queries to the search engine to obtain search results;

extracting features from at least a subset of search results

producing the term vectors from the features as a function of the term and inverted term frequencies.

36. The computing device of claim 35, and further comprising computer-program instructions executable by the processor after clustering, for:

determining that there is no match between the term/phrase and term(s)/phrase(s) from the first set of term clusters, the first set being based on the high FOO historical queries; and

responsive to the determining, identifying a match between the term/phrase and term(s)/phrase(s) from one or more of the second set of term clusters, the second set being based on the low FOO historical queries; and

responsive to identifying, generating related term suggestion(s) comprising the term(s)/phrase(s).

37. A computing device comprising at least one processor, the device further comprising:

means for mining search results via a multi-sense query, wherein the multi-sense query comprises;

means for determining terms/phrases semantically related to submitted terms/phrases, wherein semantic relationships are discovered by mining a context of the terms/phrases to determine meaning;

means for configuring a threshold frequency of occurrence (FOO) value;

means for assigning historical queries to high FOO or low FOO based on the configured threshold value;

means for generating term vectors from the search results associated with a set of high FOO historical queries previously submitted to a search engine; and

means for generating term clusters as a function of calculated similarity of term vectors, wherein calculated similarity, sim(q_i, q_k), is determined as follows;

$\mathrm{sim}<br><br>\left(q_j,q_k\right)=\underset{i=1}{\overset{d}{\sum <br><br>}}<br><br><br><br>w_{\mathrm{ij}},w_{\mathrm{ik}};<br><br>$

wherein d represents vector dimension, q represents a query, k is a dimension index, and wherein weight w for the i^th vector'"'"'s j^th term is calculated as follows;

w_ij=TF_ij×

log(N/DF_j); and

wherein TF_j represents term frequency, N is a total number of query terms, and DF_j is a number of extracted feature records that contain the i^th vector'"'"'s j^th term;

responsive to receiving a term/phrase from an entity, means for evaluating the term/phrase via the multi-sense query in view of terms/phrases in the term clusters to identify one or more related term suggestions, wherein the identifying is based on a combination of FOO and a confidence value; and

means for returning at least one suggested term list ordered by the combination of FOO and confidence value, wherein multiple suggested term lists are generated when the term/phrase matches terms in more than one term cluster.

38. The computing device of claim 37 and wherein the entity is a computer-program application and/or an end-user.

39. The computing device of claim 37, further comprising computer-program instructions executable by the processor for:

collecting means to collect historic query terms from a query log; and

determining means to determine ones of the historic query terms with the high FOO.

40. The computing device of claim 37, wherein the evaluating means further comprise:

identifying means to identify a match between the term/phrase and term(s)/phrase(s) from one or more term clusters; and

responsive to identifying, generating means to generate related term suggestion(s) comprising the term(s)/phrase(s).

41. The computing device of claim 37, wherein the generating means to generate the term clusters further comprise:

sending means to send respective ones of the high FOO historical queries to the search engine to obtain the search results;

extracting means to extract features from at least a subset of search results corresponding to the respective ones;

producing means to produce the term vectors from the features.

42. The computing device as recited in claim 37, wherein the term clusters are a first set of term clusters, and wherein the computing device further comprises:

determining means to determine that there is no match between the term/phrase and the terms/phrases; and

responsive to the determining;

making means to make a second set of term clusters from calculated similarity of term vectors, each term vector being generated from search results associated with a set of low FOO historical queries previously submitted to the search engine; and

evaluating means to evaluate the term/phrase in view of terms/phrases of the second set of term clusters to identify one or more related term suggestions.

43. The computing device of claim 42, and further comprising:

calculating means to calculate that there is no match between the term/phrase and term(s)/phrase(s) from the first set of term clusters, the first set being based on the high FOO historical queries; and

responsive to the calculating, identifying means to identify a match between the term/phrase and term(s)/phrase(s) from one or more of the second set of term clusters, the second set being based on the low FOO historical queries; and

responsive to identifying, generating means to generate related term suggestion(s) comprising the term(s)/phrase(s).