REAL-TIME-READY BEHAVIORAL TARGETING IN A LARGE-SCALE ADVERTISEMENT SYSTEM

• US 20110313844A1
• Filed: 06/17/2010
• Published: 12/22/2011
• Est. Priority Date: 06/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chandramouli, Badrish, Goldstein, Jonathan, Jin, Xin, Raman, Balan Sethu, Duan, Songyun
• Granted Patent: US 8,442,863 B2
• Time in Patent Office: Days
• US Class Current: 705/14.42
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0242 Determining effectiveness of advertisements
• CPC Class Codes: G06Q 30/0243 Comparative campaigns

Abstract

A “Real-Time-Ready Analyzer” combines a data stream management system (DSMS) with a map-reduce (M-R) framework to construct a streaming map-reduce framework that is suitable for real-time Behavioral Targeting (BT) (or other temporal queries). The Real-Time-Ready Analyzer allows users to write “dual-intent” temporal analysis queries for BT. These queries are succinct and easy to express, scale well on large-scale offline data, and can also work over real-time data. Further, the Real-Time-Ready Analyzer uses the aforementioned streaming map-reduce framework to provide dual-intent algorithms for end-to-end BT phases. Experiments using real data from an advertisement system show that the Real-Time-Ready Analyzer is very efficient and incurs orders-of-magnitude lower development effort than conventional systems.

Claims

1. A device for running temporal queries over large sets of data stored in a distributed file system, comprising:

a device for receiving one or more data sets stored in a distributed file system, said data sets comprising a plurality of time-stamped events;

a device for specifying one or more temporal queries to be run in a Map-Reduce (M-R) application;

a device for splitting the temporal queries into a set of continuous query (CQ) fragments which are then evaluated to determine a partitioning key;

using the partitioning key for partitioning and distributing the data sets to a cluster comprising a plurality of computing devices in a map phase of the M-R application;

an embedded data stream management system (DSMS) having one or more DSMS-based algorithms for executing a corresponding CQ fragment on a corresponding one of the partitioned data sets, said DSMS algorithms operating on the plurality of computing devices to output one or more events from execution of the CQ fragments on the partitioned data;

wherein output of the DSMS-based algorithms is written to an in-memory blocking queue, from which a reducer phase of the M-R application reads events synchronously relative to the time-stamp associated with each event, regardless of a DSMS output order for the events;

wherein the reducer phase of the M-R framework completes the CQ of the partitioned data by processing the events that are synchronously read from the blocking queue by performing the same computation on each data partition in parallel each of the computing devices; and

a device for outputting the results of the completed CQs to generate the results of the temporal queries.

2. The system of claim 1 wherein at least of one the data sets represents historical session data stored derived from a browsing history of one or more groups of users, said historical session data comprising time-stamped click and impression data for a plurality of ads in combination with user-specific features, said features including any of pageviews, URLs and keywords associated with the browsing history of each user.

3. The system of claim 2 wherein one or more of the temporal queries is designed to perform behavioral targeting (BT) of the users based on the historical session data to construct a user behavior profile (UBP) for each unique user.

4. The system of claim 3 wherein one or more of the temporal queries estimates a click-through rate (CTR) for feature/ad pairs for each UBP in the reduce phase of the M-R application, with the estimated CTRs being output as the results of the completed CQ.

5. The system of claim 4 wherein the estimated CTRs are used to estimate new ad CTRs for new users in real-time in response to real-time user browsing information, including recent time-stamped click and impression data for a plurality of ads in combination with user-specific features, said features including any of pageviews, URLs and keywords.

6. The system of claim 5 further comprising serving one or more ads to one or more new users in real-time based on the estimated new ad CTRs for those users.

7. The system of claim 6 further comprising an automated online ad auction, and wherein ads are automatically selected for specific positions based on bid levels for corresponding ads relative to the estimated CTRs.

8. The system of claim 2 further comprising a feature elimination process comprising:

a support-based statistical hypothesis test that retains only features having a number of associated clicks exceeding a specified minimum click level; and

wherein of the retained features, any features having a statistical correlation of positive or negative click events that is below a minimum statistical threshold are eliminated, thereby creating a reduced feature set comprising any remaining features.

9. The system of claim 8 wherein one or more of the temporal queries is designed to perform behavioral targeting (BT) of the users based on the reduced feature to construct a user behavior profile (UBP) for each unique user.

10. The system of claim 2 further comprising processing the historical session data to eliminate any data corresponding to users identified as bots.

11. A method for real-time estimation of user-specific click through rates (CTR) for ads, comprising steps for:

receiving one or more sets of historical session data derived from one or more groups of users, said historical session data comprising time-stamped click and impression data for a plurality of ads in combination with user-specific features, said features including any of pageviews, URLs and keywords;

processing the historical session data to eliminate any data corresponding to users identified as bots to generate a set of bot-free session data;

processing the bot-free session data to generate a user behavior profile (UBP) for each user in the bot-free session data;

processing the bot-free session data to eliminate statistically insignificant features by performing a statistical hypothesis test that retains only features having a number of associated clicks exceeding a specified minimum click level, and from the retained features, eliminating any features having a statistical association of positive or negative click events that is below a minimum statistical threshold, thereby creating a reduced feature set from the bot-free session data;

generating a model of click-through behavior for each ad in the bot-free data for each UBP;

for new user session data received in real-time, computing a score for each feature/ad pair based on the bot-free data and the reduced feature set for each new user based on the model of click-through behavior for each ad;

estimating a CTR for each ad from the computed score for each ad; and

serving one or more ads in real-time to each new user based on the estimated CTR for each ad for each new user.

12. The method of claim 11 wherein predicting the CTR for each ad further comprises:

choosing a predetermined number of examples of feature/ad pairs having scores closest to a current ad score; and

estimating the CTR for the current ad score as an average CTR within the selected examples.

13. The method of claim 12 further comprising an automated online ad auction, and wherein ads are automatically selected for specific positions in an ad panel presented to the user in a query results page provided in response to a user-entered keyword.

14. The method of claim 11 wherein computing a score for each feature/ad pair based on the bot-free data and the reduced feature set for each new user based on the model of click-through behavior for each ad comprises:

specifying a continuous query (CQ) for estimating the CTR, said CQ to be run in a Map-Reduce (M-R) application;

determining a partitioning key for the CQ from the bot-free session data for use in partitioning the bot-free session data, and distributing the partitioned data sets to a cluster comprising a plurality of computing devices in a map phase of the M-R application;

instantiating an embedded data stream management system (DSMS) having one or more DSMS-based algorithms for performing temporal analysis of data sets partitioned in the map phase of the M-R framework, said DSMS algorithms operating on the plurality of computing devices to output one or more events from the temporal analysis of the partitioned data;

wherein output of the DSMS-based algorithms is written to an in-memory blocking queue, from which a reducer phase of the M-R application reads events synchronously relative to the time-stamp associated with each event, regardless of a DSMS output order for the events; and

wherein the reducer phase of the M-R framework completes the CQ of the partitioned data by processing the events that are synchronously read from the blocking queue by performing the same computation on each data partition in parallel each of the computing devices to compute the score for each ad.

15. A computer-readable medium having computer executable instructions stored therein for running continuous queries over large sets of data stored in a distributed file system, said instructions comprising:

receiving one or more data sets stored in a distributed file system, said data sets comprising a plurality of time-stamped events;

processing the data sets to eliminate any data corresponding to users identified as bots;

specifying one or more temporal queries to be run in a Map-Reduce (M-R) application;

fragmenting the temporal queries into a set of continuous queries (CQ);

determining a partitioning key for each CQ from the data sets for use in partitioning the data sets and distributing the partitioned data sets to a cluster comprising a plurality of computing devices in a map phase of the M-R application;

instantiating an embedded data stream management system (DSMS) having one or more DSMS-based algorithms for performing temporal analysis of data sets partitioned in the map phase of the M-R framework, said DSMS algorithms operating on the plurality of computing devices to output one or more events from the temporal analysis of the partitioned data;

wherein output of the DSMS-based algorithms is written to an in-memory blocking queue, from which a reducer phase of the M-R application reads events synchronously relative to the time-stamp associated with each event, regardless of a DSMS output order for the events;

wherein the reducer phase of the M-R framework completes the CQ of the partitioned data by processing the events that are synchronously read from the blocking queue by performing the same computation on each data partition in parallel each of the computing devices; and

outputting the results of the completed CQs to generate the results of the temporal queries.

16. The computer-readable medium of claim 15 wherein at least of one the data sets represents historical session data stored derived from a browsing history of one or more groups of users, said historical session data comprising time-stamped click and impression data for a plurality of ads in combination with user-specific features, said features including any of pageviews, URLs and keywords associated with the browsing history of each user.

17. The computer-readable medium of claim 16 wherein one or more of the temporal queries is designed to perform behavioral targeting (BT) of the users based on the historical session data to construct a user behavior profile (UBP) for each unique user.

18. The computer-readable medium of claim 17 wherein one or more of the temporal queries estimates a click-through rate (CTR) for feature/ad pairs for each UBP in the reduce phase of the M-R application, with the estimated CTRs being output as the results of the completed CQ.

19. The computer-readable medium of claim 18 wherein the estimated CTRs are used to estimate new ad CTRs for new users in real-time in response to real-time user browsing information, including recent time-stamped click and impression data for a plurality of ads in combination with user-specific features, said features including any of pageviews, URLs and keywords.

20. The computer-readable medium of claim 16 further comprising a feature elimination process, comprising:

a support-based statistical hypothesis test that retains only features having a number of associated clicks exceeding a specified minimum click level; and

wherein of the retained features, any features having a statistical association of positive or negative click events that is below a minimum statistical threshold are eliminated, thereby creating a reduced feature set comprising any remaining features.