System for generating query suggestions by integrating valuable query suggestions with experimental query suggestions using a network of users and advertisers

• US 7,849,080 B2
• Filed: 07/30/2007
• Issued: 12/07/2010
• Est. Priority Date: 04/10/2007
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chang, Chi-Chao, Tayal, Manish, Anastasakos, Tasos
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Fan; Shiow-Jy
• Application Number:
  US11/830,753
• Publication Number:
  US 20080256061A1
• Time in Patent Office: 1,226 Days
• Field of Search: 707 3- 5, 707/E17.017, 707/999.005, 707/706, 707/748, 707/767, 707/751, 707/E17.014, 709/218
• US Class Current: 707/723
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0244 Optimization
• CPC Class Codes: G06Q 30/0256 User search
• CPC Class Codes: G06Q 30/0277 Online advertisement

Abstract

A system is described for generating query suggestions by integrating valuable query suggestions with experimental query suggestions using a network of users and advertisers. The system may include a memory, an interface, and a processor. The memory may store a historical dataset, a plurality of query suggestions, a plurality of query suggestion values, a query exploit set, a query explore set, and a data describing a network. The processor may identify the plurality of query suggestions in the historical dataset and generate data describing the network based on the historical dataset. The processor may calculate the query suggestion value for each query suggestion and may rank the query suggestions based on the query suggestion values. The processor may generate an exploit set comprising the top ranked query suggestions and an explore set comprising the remainder. The processor may suggest the query suggestions in the exploit set and the explore set.

Claims

1. A method for generating query suggestions by integrating valuable query suggestions with experimental query suggestions using a network of users and advertisers, the method comprising:

identifying a plurality of query suggestions in a historical dataset, the historical dataset comprising queries searched for by users and advertisements selected by the users after searching for the queries, wherein the query suggestions comprise queries identified as having some relevancy to the queries searched for by the users;

generating, from the historical dataset, a data describing a network comprising a plurality of query items representing queries linked to a plurality of advertisement items representing advertisements;

calculating a query suggestion value for each query suggestion in the plurality of query suggestions using the data describing the network, wherein the query suggestion value of each query suggestion is based on a number of advertisements attributable to each query suggestion which are selected by the users;

ranking the plurality of query suggestions, in descending order, based on the query suggestion value of each query suggestion;

generating a query exploit set and a query explore set, wherein the query exploit set comprises the top N ranked query suggestions and the query explore set comprises the remainder of the query suggestions, further wherein N comprises any integer; and

suggesting, by a processor, the query suggestions in the exploit set and the explore set, wherein the query suggestions in the exploit set are suggested more frequently than the query suggestions in the explore set.

2. The method of claim 1 further comprising determining a relevance value for each suggested query in the query explore set.

3. The method of claim 2 further comprising:

ranking the suggested queries in the query explore set based on the relevance value of each suggested query; and

suggesting the higher ranked query suggestions more frequently than the lower ranked query suggestions.

4. The method of claim 1 wherein suggesting the query suggestions in the exploit set more frequently than the query suggestions in the explore set further comprises:

suggesting the query suggestions in the exploit set and the query suggestions in the explore set for a period of time T, wherein T comprises any period of time, further wherein the query suggestions in the exploit set are suggested more frequently than the query suggestions in the explore set;

re-generating, after the period of time T elapses, from the historical dataset and a dataset relating to the period of time T, the data describing the network comprising the plurality of query items representing queries linked to the plurality of advertisement items representing advertisements;

re-calculating, after the period of time T, the query suggestion value for each query suggestion in the plurality of query suggestions using the data describing the network;

re-ranking, after the period of time T, the plurality of query suggestions, in descending order, based on the query suggestion value of each query suggestion;

re-generating, after the period of time T, the query exploit set and the query explore set, wherein the query exploit set comprises the top N ranked query suggestions and the query explore set comprises the remainder of the query suggestions, further wherein N comprises any integer; and

suggesting the query suggestions in the exploit set and the query suggestions in the explore set, wherein the query suggestions in the exploit set are suggested more frequently than the query suggestions in the explore set.

5. The method of claim 1 wherein each advertisement item in the plurality of advertisement items comprises an online advertisement of an advertiser.

6. The method of claim 5 further comprising linking an advertisement item to a query item in the data describing the network, via a query-advertisement link item, when the historical dataset indicates that a user clicked on the advertisement item after searching for the query item.

7. The method of claim 1 wherein the query suggestions are suggested to a user performing a search query.

8. The method of claim 1 wherein the query suggestions suggested to a data serving system, further wherein the query suggestions are used by the data serving system to identify a set of advertisements to serve to a user.

9. The method of claim 1 further comprising:

splitting the query explore set into an online query explore set and an offline query explore set; and

suggesting the query suggestions in the exploit set and the online explore set, wherein the query suggestions in the exploit set are suggested more frequently than the query suggestions in the online explore set.

10. A method for generating query suggestions by integrating valuable query suggestions with online and offline experimental query suggestions using a network of users and advertisers, the method comprising:

(a) identifying a plurality of query suggestions in a historical dataset, the historical dataset comprising queries searched for by users and advertisements selected by the users after searching for the queries, wherein the query suggestions comprise queries identified as having some relevancy to the queries searched for by the users;

(b) generating, from the historical dataset, a data describing a network comprising a plurality of query items representing queries linked to a plurality of advertisement items representing advertisements;

(c) calculating a query suggestion value for each query suggestion in the plurality of query suggestions using the data describing the network, wherein the query suggestion value of each query suggestion is based on a number of advertisements attributable to each query suggestion which are selected by the users;

(d) ranking the plurality of query suggestions, in descending order, based on the query suggestion value of each query suggestion;

(e) generating a query exploit set comprising the top N ranked query suggestions, wherein N comprises any integer, and a query explore set comprising the remainder of the query suggestions;

(f) calculating a relevance value of each query suggestion in the query explore set;

(g) ranking each query suggestion in the query explore set based on the relevance value of each query suggestion;

(h) generating an online query explore set and an offline query explore set wherein the online query explore set comprises the top half of the ranked query suggestions in the query explore set and the offline query explore set comprises the bottom half of the ranked query suggestions in the query explore set;

(i) suggesting, by a processor, the query suggestions in the exploit set and the online query explore set, wherein the query suggestions in the exploit set are suggested more frequently than the query suggestions in the online query explore set; and

(j) rotating the queries in the offline query explore set and the online query explore set after the passage of a period of time.

11. The method of claim 10 further comprising:

(k) retrieving an updated historical dataset after the passage of a second period of time; and

(l) repeating steps (a)-(k).

12. The method of claim 10 further comprising linking an advertisement item to a query item in the data describing the network when the historical dataset indicates a user clicked on the advertisement item after searching for the query item.

13. The method of claim 10 wherein the query suggestions are associated with a plurality of matching systems.

14. The method of claim 10 wherein the query suggestions are communicated to an advertisement serving system.

15. The method of claim 14 wherein the suggested queries are used by the advertisement serving system to identify a set of advertisements to serve to a user.

16. A system for generating query suggestions by integrating valuable query suggestions with experimental query suggestions using a network of users and advertisers, the system comprising:

a memory to store a historical dataset comprising queries searched for by users and advertisements selected by the users after searching for the queries, a data describing a network comprising a plurality of query items representing queries linked to a plurality of advertisement items representing advertisements, a plurality of query suggestion values, a query exploit set, and a query explore set;

an interface connected to the memory, the interface operative to communicate query suggestions; and

a processor operatively connected to the memory and the interface, the processor operative to identify a plurality of query suggestions in the historical dataset, wherein the query suggestions comprise queries identified as having some relevancy to the queries searched for by the users, generate the data describing the network based on the historical dataset, calculate the query suggestion value for each query suggestion in the plurality of query suggestions using the data describing the network, wherein the query suggestion value of each query suggestion is based on a number of advertisements attributable to each query suggestion which are selected by the users, rank the plurality of query suggestions, in descending order, based on the query suggestion value of each query suggestion, generate a query exploit set comprising the top ranked query suggestions and a query explore set comprising the remainder of the query suggestions and suggest, via the interface, the query suggestions in the exploit set and the explore set, wherein the query suggestions in the exploit set are suggested more frequently than the query suggestions in the explore set.

17. The system of claim 16 wherein the query suggestion are communicated to an advertisement serving system via the interface.

18. The system of claim 16 wherein the processor stores in the memory a subset of the query suggestions in the explore set, further wherein the query suggestions in the subset are not suggested.

19. The system of claim 18 wherein the processor rotates the query suggestions in the subset and the query suggestions in the explore set after a period of time elapses.

20. The system of claim 16 wherein after a second period of time elapses the processor retrieves a second historical dataset, regenerate the data describing the network based on the second historical dataset, recalculates the query suggestion value for each query suggestion using the regenerated network, re-ranks the plurality of query suggestions, in descending order, based on the recalculated query suggestion value of each query suggestion, regenerates a query exploit set comprising the top ranked query suggestions and a query explore set comprising the remainder of the query suggestions and suggests, via the interface, the query suggestions in the regenerated exploit set and the regenerated explore set, wherein the query suggestions in the regenerated exploit set are suggested more frequently than the query suggestions in the regenerated explore set.