System for building a data structure representing a network of users and advertisers

• US 20080256056A1
• Filed: 04/10/2007
• Published: 10/16/2008
• Est. Priority Date: 04/10/2007
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chang, Chi-Chao, Tayal, Manish, Anastasakos, Tasos
• Application Number:
  US11/786,326
• Publication Number:
  US 20080256056A1
• Time in Patent Office: Days
• US Class Current: 707/5
• 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 building a data structure representing a network of advertisers and users. The system may include a memory and a processor. The memory may be operatively connected to the processor and may store a historical dataset comprising of a plurality of query items and advertisement items, a plurality of query-advertisement link items, a weight, a data structure and a condition. The processor may identify the historical dataset, and link the query items to the advertisement items to generate query-advertisement link items. The processor may determine the weight of each query-advertisement link item and may store the query-advertisement link items and the weight in the data structure if the query-advertisement link item satisfies the condition.

Claims

1. A method for building a data structure representing a network of users and advertisers, the method comprising:

identifying a historical dataset comprising a plurality of query items wherein each query item is associated with a set of advertisement items;

linking each query item in the plurality of query items to each advertisement item in the set of advertisement items associated with the query item to generate a plurality of query-advertisement link items;

determining a weight for each query-advertisement link item;

storing each query-advertisement link item and the weight calculated for each query-advertisement link item in a data structure if the query-advertisement link item satisfies a condition.

2. The method of claim 1 wherein each query item in the plurality of query items comprises a search performed by a user.

3. The method of claim 2 wherein the set of advertisement items associated with each query item comprises an ad listing of an advertiser that was clicked on by the user after searching for the query item.

4. The method of claim 1 wherein the condition is satisfied for each query-advertisement link item if the query advertisement link item does not exist in the data structure.

5. The method of claim 1 wherein the weight of each query-advertisement link item comprises a total number of click throughs attributable to the query-advertisement link item.

6. The method of claim 5 wherein the total number of clicks may represent the number of times a plurality of users clicked on the advertisement item associated with the query-advertisement link item after searching for the query item associated with the query-advertisement link item.

7. The method of claim 5 wherein the total number of click throughs for the query-advertisement link item comprises the total number of equivalent query-advertisement link items in the historical dataset.

8. The method of claim 1 wherein the data structure comprises a database table.

9. The method of claim 1 further comprising rebuilding the data structure at a regular interval of time with an updated historical dataset.

10. A method of constructing a bipartite graph out of click log data, comprising:

identifying a set of unique queries in the click log data;

creating a set of query nodes in a bipartite graph wherein each node comprises a query in the set of unique queries;

identifying a set of unique ads in the click log data;

creating a set of ad nodes in the bipartite graph wherein each ad node comprises an ad in the set of unique ads;

identifying a set of clicks in the click log data wherein each click comprises a query and an ad;

building an edge from each query node in the set of query nodes to each ad node in the set of ad nodes if the set of clicks contains a click comprising the query node and the ad node;

and storing the query nodes in the bipartite graph, the ad nodes in the bipartite graph, and each built edge in a data structure.

11. The method of claim 10 wherein the edge comprises a weight.

12. The method of claim 11 wherein the weight comprises a total number of click throughs.

13. The method of claim 10 wherein the data structure comprises a database.

14. The method of claim 10 further comprising rebuilding the bipartite graph after a period of time T.

15. A system for building a data structure representing a network of users and advertisers, comprising:

a memory to store a historical dataset comprising a plurality of query items wherein each query item is associated with a set of advertisement items, a plurality of query-advertisement link items, a weight, a data structure, and a condition; and

a processor operatively connected to the memory, the processor operative to identify the historical dataset, link each query item in the plurality of query items to each advertisement item in the set of advertisement items associated with the query item to generate a plurality of query-advertisement link items, determine the weight of each query-advertisement link item and store each query-advertisement link item and the weight in the data structure if the query-advertisement link item satisfies the condition.

16. The system of claim 15 wherein each query item in the plurality of query items comprises a search performed by a user.

17. The system of claim 16 wherein the set of advertisement items associated with each query item comprises an ad listing of an advertiser that was clicked on by the user after searching for the query item.

18. The system of claim 15 wherein the condition is satisfied for each query-advertisement link item if the query advertisement link item does not exist in the data structure.

19. The system of claim 15 wherein the weight of each query-advertisement link item comprises a total number of click throughs attributable to the query-advertisement link item.

20. The method of claim 15 wherein the data structure comprises a database table.