EDGE ATTRIBUTE AGGREGATION IN A DIRECTED GRAPH

• US 20100217695A1
• Filed: 02/26/2009
• Published: 08/26/2010
• Est. Priority Date: 02/26/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Alnahlawi, Mahmoud
• Granted Patent: US 8,095,560 B2
• Time in Patent Office: Days
• US Class Current: 705/34
• CPC Class Codes: G06Q 20/102 Bill distribution or payments
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0244 Optimization
• CPC Class Codes: G06Q 30/0273 Determination of fees for advertising
• CPC Class Codes: G06Q 30/04 Billing or invoicing

Abstract

Methods and apparatus are described by which edge attribute data relating to a system that may be represented by a directed graph may be efficiently aggregated despite the presence of virtual entities in the system for which edge attribute data aggregation is not useful or meaningful.

Claims

1. A computer-implemented method for aggregating event data from an advertising system for billing purposes, the method comprising:

receiving the event data for a time period from the advertising system, the event data comprising a plurality of event data records each corresponding to an advertising event occurring during the time period, each event data record comprising a sequence of one or more hop data records, each hop data record including a source entity identifier corresponding to a source entity from whom payment for the corresponding advertising event is owed, a target entity identifier corresponding to a target entity to whom payment for the corresponding advertising event is owed, a deal identifier corresponding to a deal between the source entity and the target entity, and a payment amount relating to the advertising event;

for each of selected ones of the hop data records for which the target entity identifier corresponds to a virtual entity, generating a virtual hop data record including the source entity identifier and the deal identifier from the selected hop data record and the target entity identifier and payment amount from a next hop data record immediately following the selected hop data record in the event data;

aggregating the payment amounts in the event data for each unique combination of source entity, target entity, and deal using the virtual hop data records and disregarding the selected hop data records; and

facilitating payment for each of the advertising events represented in the event data using the aggregated payment amounts.

2. The method of claim 1 wherein generating the virtual hop data records comprises:

sequentially evaluating the hop data records in the event data;

for each of the selected hop data records, caching the source entity identifier and the deal identifier; and

for each of the next hop data records following one of the selected hop data records, generating the corresponding virtual hop data record by replacing the source entity identifier and the deal identifier in the next hop data record with the cached source entity identifier and the cached deal identifier from the selected hop data record preceding the next hop data record.

3. The method of claim 1 wherein aggregating the payment amounts is done incrementally as each virtual hop data record is generated.

4. The method of claim 1 wherein aggregating the payment amounts is done after all of the virtual hop data records are generated.

5. The method of claim 1 wherein the advertising system comprises an advertising exchange in which the source entities and target entities are participants, and wherein the virtual entities represent one or more of the participants.

6. A computer program product for aggregating event data from an advertising system for billing purposes, the computer program product comprising at least one tangible computer readable medium having computer program instructions stored therein, the computer program instructions being configured to cause at least one computing device to:

receive the event data for a time period from the advertising system, the event data comprising a plurality of event data records each corresponding to an advertising event occurring during the time period, each event data record comprising a sequence of one or more hop data records, each hop data record including a source entity identifier corresponding to a source entity from whom payment for the corresponding advertising event is owed, a target entity identifier corresponding to a target entity to whom payment for the corresponding advertising event is owed, a deal identifier corresponding to a deal between the source entity and the target entity, and a payment amount relating to the advertising event;

for each of selected ones of the hop data records for which the target entity identifier corresponds to a virtual entity, generate a virtual hop data record including the source entity identifier and the deal identifier from the selected hop data record and the target entity identifier and payment amount from a next hop data record immediately following the selected hop data record in the event data;

aggregate the payment amounts in the event data for each unique combination of source entity, target entity, and deal using the virtual hop data records and disregarding the selected hop data records; and

facilitate payment for each of the advertising events represented in the event data using the aggregated payment amounts.

7. The computer program product of claim 6 wherein the computer program instructions are configured to cause the at least one computing device to generate the virtual hop data records by:

sequentially evaluating the hop data records in the event data;

for each of the selected hop data records, caching the source entity identifier and the deal identifier; and

for each of the next hop data records following one of the selected hop data records, generating the corresponding virtual hop data record by replacing the source entity identifier and the deal identifier in the next hop data record with the cached source entity identifier and the cached deal identifier from the selected hop data record preceding the next hop data record.

8. The computer program product of claim 6 wherein the computer program instructions are configured to cause the at least one computing device to aggregate the payment amounts incrementally as each virtual hop data record is generated.

9. The computer program product of claim 6 wherein the computer program instructions are configured to cause the at least one computing device to aggregate the payment amounts after all of the virtual hop data records are generated.

10. The computer program product of claim 6 wherein the advertising system comprises an advertising exchange in which the source entities and target entities are participants, and wherein the virtual entities represent one or more of the participants.

11. An online advertising exchange system operating in a network and comprising at least one computing device configured to:

connect advertising inventory of participating online publishers with advertising content of participating advertisers to generate advertising events via the network;

receive event data for a time period via the network, the event data comprising a plurality of event data records each corresponding to an advertising event occurring during the time period, each event data record comprising a sequence of one or more hop data records, each hop data record including a source entity identifier corresponding to a source entity from whom payment for the corresponding advertising event is owed, a target entity identifier corresponding to a target entity to whom payment for the corresponding advertising event is owed, a deal identifier corresponding to a deal between the source entity and the target entity, and a payment amount relating to the advertising event;

for each of selected ones of the hop data records for which the target entity identifier corresponds to a virtual entity, generate a virtual hop data record including the source entity identifier and the deal identifier from the selected hop data record and the target entity identifier and payment amount from a next hop data record immediately following the selected hop data record in the event data, each virtual entity representing one or more participants in the advertising exchange;

aggregate the payment amounts in the event data for each unique combination of source entity, target entity, and deal using the virtual hop data records and disregarding the selected hop data records; and

facilitate payment for each of the advertising events represented in the event data via the network using the aggregated payment amounts.

12. The online advertising exchange system of claim 11 wherein the at least one computing device is configured to generate the virtual hop data records by:

sequentially evaluating the hop data records in the event data;

for each of the selected hop data records, caching the source entity identifier and the deal identifier; and

for each of the next hop data records following one of the selected hop data records, generating the corresponding virtual hop data record by replacing the source entity identifier and the deal identifier in the next hop data record with the cached source entity identifier and the cached deal identifier from the selected hop data record preceding the next hop data record.

13. The online advertising exchange system of claim 11 wherein the at least one computing device is configured to aggregate the payment amounts incrementally as each virtual hop data record is generated.

14. The online advertising exchange system of claim 11 wherein the at least one computing device is configured to aggregate the payment amounts after all of the virtual hop data records are generated.

15. A computer-implemented method for aggregating edge attributes relating to a directed graph representation of a system, wherein the directed graph representation comprises a plurality of paths, each path comprising a plurality of nodes interconnected by a plurality of edges, the method comprising:

collecting path data in which each of a subset of the paths of the directed graph representation is represented by a path data record, each path data record comprising a sequence of one or more edge data records, each edge data record corresponding to one of the edges and including a source node identifier corresponding to a source node from which the corresponding edge originates, a target node identifier corresponding to a target node at which the corresponding edge terminates, and a plurality of attributes characterizing a relationship between the source node and the target node; and

for each of selected ones of the edge data records for which the target node identifier corresponds to a virtual node, generating a virtual edge data record including the source node identifier and a first attribute from the selected edge data record and the target node identifier and a second attribute from a next edge data record immediately following the selected edge data record in the corresponding path data record; and

aggregating a third edge attribute in the path data for each unique combination of a first plurality of edge attributes using the virtual edge data records and disregarding the selected edge data records.

16. The method of claim 15 wherein generating the virtual edge data records comprises:

sequentially evaluating the edge data records in the path data;

for each of the selected edge data records, caching the source node identifier and the first attribute from the selected edge data record; and

for each of the next edge data records following one of the selected edge data records, generating the corresponding virtual edge data record by replacing the source node identifier and the first attribute in the next hop data record with the cached source node identifier and the cached first attribute from the selected edge data record preceding the next edge data record.

17. A computer program product for aggregating edge attributes relating to a directed graph representation of a system, wherein the directed graph representation comprises a plurality of paths, each path comprising a plurality of nodes interconnected by a plurality of edges, the computer program product comprising at least one tangible computer readable medium having computer program instructions stored therein, the computer program instructions being configured to cause at least one computing device to:

collect path data in which each of a subset of the paths of the directed graph representation is represented by a path data record, each path data record comprising a sequence of one or more edge data records, each edge data record corresponding to one of the edges and including a source node identifier corresponding to a source node from which the corresponding edge originates, a target node identifier corresponding to a target node at which the corresponding edge terminates, and a plurality of attributes characterizing a relationship between the source node and the target node; and

for each of selected ones of the edge data records for which the target node identifier corresponds to a virtual node, generate a virtual edge data record including the source node identifier and a first attribute from the selected edge data record and the target node identifier and a second attribute from a next edge data record immediately following the selected edge data record in the corresponding path data record; and

aggregate a third edge attribute in the path data for each unique combination of a first plurality of edge attributes using the virtual edge data records and disregarding the selected edge data records.

18. The computer program product of claim 17 wherein the computer program instructions are configured to cause the at least one computing device to generate the virtual edge data records by:

sequentially evaluating the edge data records in the path data;

for each of the selected edge data records, caching the source node identifier and the first attribute from the selected edge data record; and

for each of the next edge data records following one of the selected edge data records, generating the corresponding virtual edge data record by replacing the source node identifier and the first attribute in the next hop data record with the cached source node identifier and the cached first attribute from the selected edge data record preceding the next edge data record.