Inferring search category synonyms from user logs

• US 7,627,548 B2
• Filed: 11/22/2005
• Issued: 12/01/2009
• Est. Priority Date: 11/22/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Liu, Zhiyan, Riley, Michael D.
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Quader; Fazlul
• Application Number:
  US11/283,833
• Publication Number:
  US 20070118512A1
• Time in Patent Office: 1,470 Days
• Field of Search: 707/2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Systems and methods for inferring category synonyms from prior result data may include identifying prior query data including query information and category information relating to the prior result data; determining whether the query information is a synonym for the category information; and using the query information and the category information in subsequent search requests if it is determined that the query information is a synonym for the category information.

Claims

1. A method performed by a server, the method comprising:

identifying, by a processor of the server, prior query data, where the prior query data includes at least query term information and category information associated with search results returned based on the query term information, where the prior query data further includes at least;

query terms associated with a user query for business listing information,

a resulting business name returned in response to the user query, and

a resulting business category associated with the resulting business name;

determining, by the processor, whether the category information is a synonym for the query term information, where the determining comprises;

determining whether the prior query data relates to a name query or a categorical query,

determining whether the query terms are a candidate synonym of the resulting business category when the prior query data relates to a categorical query,

determining whether a query, category pair, associated with the prior query data, is a hyponym,

rejecting the query terms as a synonym of the resulting business category when the query, category pair, associated with the prior query data, is a hyponym, and

accepting the query terms as a synonym of the resulting business category when the query, category pair associated with the prior query data is not a hyponym;

receiving, by the processor, a subsequent search request relating to the query term information or the category information;

refining, by the processor, the subsequent search request based on the query term information and the category information when the query term information is a synonym for the category information;

performing, by the processor, a search based on the refined search request; and

providing, by the processor, search results based on the search.

2. The method of claim 1, wherein identifying prior query data further comprises:

determining whether the prior query data had received a previous indication of relevancy.

3. The method of claim 2, wherein the previous indication of relevancy includes receiving a predefined user action associated with the prior query data.

4. The method of claim 3, wherein the predefined user action includes receiving a user selection of a driving directions request.

5. The method of claim 1, wherein determining whether the prior query data relates to a name query or a categorical query, further comprises:

determining whether the query term information relates to a request for a business name or a business category.

6. The method of claim 5, wherein determining whether the query term information relates to a request for a business name or a business category, further comprises:

determining a name perplexity for the query term information, where query term information having higher name perplexity corresponds to categorical queries and query term information having lower name perplexity corresponds to name queries.

7. The method of claim 1, wherein determining whether a query, category pair associated with the prior query data is a hyponym comprises:

calculating an F-measure for the query, category pair.

8. The method of claim 7, wherein the F-measure for the query, category pair is calculated in accordance with the expression:

$F<br><br>\text{-}<br><br>\mathrm{measure}<br><br>\left(\mathrm{query},\mathrm{category}\right)=\frac{P<br><br>\left(\mathrm{query},\mathrm{category}\right)}{\left(a\times <br><br>P<br><br>\left(\mathrm{category}\right)+\left(1-a\right)\times <br><br>P<br><br>\left(\mathrm{query}\right)\right)},$

where P(n) denotes a probability of occurrence in the prior query data, and ‘

a’

is a predefined variable for balancing recall and precision.

9. The method of claim 8, wherein ‘

a’

is within the range of approximately 0.7 to 0.9.

10. The method of claim 8, wherein ‘

a’

is approximately 0.85.

11. A system, comprising:

means for determining whether prior query data and prior category data associated with prior search results comprise category synonyms, where the prior query data includes at least;

query terms associated with a user query for business listing information,

a resulting business name returned in response to the user query, and

a resulting business category associated with the resulting business name;

where the means for determining includes;

means for determining whether the prior query data relates to a name query or a categorical query,

means for determining whether the query terms are a candidate synonym of the resulting business category when the prior query data relates to a categorical query,

means for determining whether a query, category pair, associated with the prior query data, is a hyponym,

means for rejecting the query terms as a synonym of the resulting business category when the query, category pair, associated with the prior query data, is a hyponym, and

means for accepting the query terms as a synonym of the resulting business category when the query, category pair, associated with the prior query data, is not a hyponym;

means for receiving a subsequent search request relating to the prior category data;

means for refining the subsequent search request based on the prior query data when the prior query data and the prior category data comprise category synonyms;

means for performing a search based on the refined search request; and

means for providing search results based on the search.

12. The system of claim 11, wherein the means for determining whether prior query data and prior category data associated with prior search results comprise category synonyms further comprises:

means for determining whether the prior search results are good search results; and

means for determining whether the prior query data and the prior category data included within the prior search results comprise category synonyms when the prior search results are determined to be good search results.

13. The system of claim 12, wherein the means for determining whether the prior search results are good search results further comprises:

means for determining whether a desirable user action has occurred in association with the prior search results.

14. A device comprising:

logic to identify historical log data including at least one query, category pair associated with a prior search request, where the query of the query, category pair is a query for business listing information, and where the historical log data further includes at least;

query terms associated with the query,

a resulting business name returned in response to the query, and

a resulting business category associated with the resulting business name;

logic to determine whether the query in the query, category pair is a name query or a categorical query;

logic to determine whether the query is a synonym of the category when the query is determined to be a categorical query, where the logic to determine whether the query is a synonym of the category includes;

logic to determine whether the query terms are a candidate synonym of the resulting business category when the query is a categorical query,

logic to determine whether the query, category pair is a hyponym,

logic to reject the query terms as a synonym of the resulting business category when the query, category pair is determined to be a hyponym, and

logic to accept the query terms as a synonym of the resulting business category when the query, category pair is not a hyponym;

logic to receive a search request relating to the query or the category;

logic to refine the received search request based on the query, category pair when the query is a synonym of the category;

logic to perform a search based on the refined search request; and

logic to provide search results based on the search.

15. The device of claim 14, wherein the logic to determine whether the query is a synonym of the category, further comprises logic to determine whether the query is a hyponym of the category.

16. A computer-readable-memory device containing instructions for controlling a processor to perform a method, comprising:

identifying prior search result data, where the prior search result data includes at least a query term and a result category, where the prior search result data further includes at least;

query terms associated with a user query for business listing information,

a resulting business name returned in response to the user query, and

a resulting business category associated with the resulting business name;

determining whether the query term is a synonym for the result category, where the determining includes;

determining whether the prior search result data relates to a name query or a categorical query,

determining whether the query terms are a candidate synonym of the resulting business category when the prior search result data relates to a categorical query,

determining whether a query, category pair, associated with the prior search result data, is a hyponym,

rejecting the query terms as a synonym of the resulting business category when the query, category pair, associated with the prior search result data, is a hyponym, and

accepting the query terms as a synonym of the resulting business category when the query, category pair, associated with the prior search result data, is not a hyponym;

receiving a subsequent search request relating to the result category;

refining the subsequent search request based on the query term when the query term is a synonym for the result category;

performing a search based on the refined search request; and

providing search results based on the search.

17. A method performed by a server, the method comprising:

receiving, by a processor of the server, a search query from a client;

identifying, by the processor, a result category based on the received search query;

identifying, by the processor, category synonyms for the identified result category based on prior query data, where the prior query data includes at least;

query terms associated with a user query for business listing information,

a resulting business name returned in response to the user query, and

a resulting business category associated with the resulting business name, and

where the identifying category synonyms comprises;

determining whether the prior query data relates to a name query or a categorical query,

determining whether the query terms are a candidate synonym of the resulting business category when the prior query data relates to a categorical query,

determining whether a query, category pair, associated with the prior query data, is a hyponym,

rejecting the query terms as a synonym of the resulting business category when the query, category pair, associated with the prior query data, is a hyponym, and

accepting the query terms as a synonym of the resulting business category when the query, category pair, associated with the prior query data, is not a hyponym;

performing, by the processor, a search based on the received search query, the result category, and the identified category synonyms; and

providing, by the processor, search results based on the search.

18. The method of claim 17, wherein the performing a search further comprises:

performing a business name search based on the received query;

performing a business name search based on the identified category synonyms; and

performing a result category search based on the identified result category.

19. The method of claim 18, wherein the performing a result category search based on the identified result category comprises an exact match search resulting in exact matches to identified result categories.