Overspend control in a messaging platform

• US 10,600,080 B1
• Filed: 03/14/2014
• Issued: 03/24/2020
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Inventors: Andersen, Reid, Agrawal, Parag, Srivastava, Utkarsh, Kim, Hyun Duk
• Primary Examiner(s): Detweiler, James M
• Application Number:
  US14/214,466
• Time in Patent Office: 2,202 Days
• Field of Search: None
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/435 Filtering based on additional data, e.g. user or group profiles
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/0247 Calculate past, present or future revenues
• CPC Class Codes: G06Q 30/0249 based upon budgets or funds
• CPC Class Codes: G06Q 30/0255 based on user history
• CPC Class Codes: G06Q 30/0275 Auctions

Abstract

A real-time messaging platform allows advertiser accounts to pay to insert candidate messages into the message streams requested by account holders. To accommodate multiple advertisers, the messaging platform controls an auction process that determines which candidate messages are selected for inclusion in a requested account holder'"'"'s message stream. Selection is based on a bid for the candidate message, the message stream that is requested, and a variety of other factors that vary depending upon the implementation. The process for selection of candidate messages generally includes the following steps, though any given step may be omitted or combined into another step in a different implementation: targeting, filtering, prediction, ranking, and selection.

Claims

1. A method comprising:

receiving, at a messaging platform that publishes message streams, including a message stream of a first account holder of the messaging platform, a request, from a computing device associated with a second account holder of the messaging platform, for the message stream of the first account holder;

selecting two or more ad campaigns resident on the messaging platform, each selected ad campaign having a budget and at least one candidate message;

calculating a current spend for each of the selected ad campaigns, the current spend representing a portion of the budget already spent by the respective ad campaign;

determining an engagement time distribution by at least applying a first smoothing distribution to a first tunable parameter to generate a first product, applying a second smoothing distribution to a second tunable parameter to generate a second product, and combining the first product and the second product;

calculating an outstanding spend for each of the selected ad campaigns based on a time at which the messaging platform received the request, the engagement time distribution, account holders that received but did not yet engage with one or more candidate messages from the respective ad campaign and a predicted clickthrough rate, wherein the predicted clickthrough rate is calculated based on a features vector and a weights vector, wherein the features vector comprises values of one or more of a message feature or an account feature, and wherein the weights vector comprises weight values for each of the features in the features vector;

calculating a total outstanding spend for each of the selected ad campaigns by adding the outstanding spend of the respective ad campaign to the current spend of the respective ad campaign;

identifying, as potential candidate messages, candidate messages from the selected ad campaigns with total outstanding spends that are less than the budget of their respective ad campaigns;

calculating, for only each potential candidate message, a likelihood value representing a likelihood of future engagement with the respective potential candidate message by one or more of the account holders if the respective potential candidate message was published in the requested message stream;

ranking the potential candidate messages based on the calculated likelihood values;

selecting, based on the ranking of the potential candidate messages, at least one candidate message for inclusion in the requested message stream; and

sending the requested message stream to the second account holder via the computing device, wherein the requested message stream includes the selected at least one candidate message.

2. The method of claim 1, wherein the outstanding spend for one of the selected ad campaigns is further calculated based on

a callback rate determined based on previous publications of candidate messages of the selected ad campaign to account holders of the messaging platform.

3. The method of claim 2, wherein the callback rate is a percentage of served candidate messages that were previously presented to any account holder of the messaging platform and in response received one or more impressions from any of the account holders of the messaging platform.

4. The method of claim 3, wherein the callback rate is a percentage of the served candidate messages that have received one or more impressions that have also received one or more engagements from any of the account holders of the messaging platform.

5. The method of claim 3, wherein the engagement time distribution further represents a likelihood that a served candidate message that receives one or more impressions is going to receive an engagement in a specified interval of time.

6. The method of claim 1, wherein each of the ad campaigns pays the messaging platform based on a number of engagements received by the messaging platform for the ad campaign'"'"'s published candidate messages.

7. The method of claim 1, wherein each of the ad campaigns pays the messaging platform based on a number of engagements received by the messaging platform for each of a plurality of different engagement categories, and wherein at least two of the engagement categories have different costs.

8. The method of claim 1, wherein at least one of the selected ad campaigns has a targeting strategy selected from a group consisting of keyword targeting, account targeting, demographic targeting, lookalike targeting, recent follow targeting, temporal targeting, retargeting, production targeting, and consumption targeting.

9. The method of claim 1, wherein calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes modeling the likelihood of engagement based on a logistic regression analysis of a history of engagements by account holders of the messaging platform with previous candidate messages presented to the respective account holders.

10. The method of claim 1, wherein calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes applying machine learning to a history of engagements by respective account holders in the one or more account holders with previous candidate messages in order to model the likelihood of engagement for each respective account holder as:

11. The method of claim 10, wherein applying the machine learning includes analyzing, for each respective account holder of the one or more account holders, the history of engagement by the respective account holder with previous candidate messages using logistic regression.

12. The method of claim 1, wherein calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes modeling, for each account holder in the one or more account holders, a likelihood of engagement with the potential candidate message via a machine learning analysis of a history of engagement by the account holder with previous candidate messages presented to the account holder.

13. A non-transitory computer-readable storage medium comprising instructions executable by a processor, the instructions for:

receiving, at a messaging platform that publishes message streams, including a message stream of a first account holder of the messaging platform, a request, from a computing device associated with a second account holder of the messaging platform, for the message stream of the first account holder;

selecting two or more ad campaigns resident on the messaging platform, each selected ad campaign having a budget and at least one candidate message;

calculating a current spend for each of the selected ad campaigns, the current spend representing a portion of the budget already spent by the respective ad campaign;

determining an engagement time distribution by at least applying a first smoothing distribution to a first tunable parameter to generate a first product, applying a second smoothing distribution to a second tunable parameter to generate a second product, and combining the first product and the second product;

calculating an outstanding spend for each of the selected ad campaigns based on a time at which the messaging platform received the request, the engagement time distribution, account holders that received but did not yet engage with one or more candidate messages from the respective ad campaign and a predicted clickthrough rate, wherein the predicted clickthrough rate is calculated based on a features vector and a weights vector, wherein the features vector comprises values of one or more of a message feature or an account feature, and wherein the weights vector comprises weight values for each of the features in the features vector;

calculating a total outstanding spend for each of the selected ad campaigns by adding the outstanding spend of the respective ad campaign to the current spend of the respective ad campaign;

identifying, as potential candidate messages, candidate messages from the selected ad campaigns with total outstanding spends that are less than the budget of their respective ad campaigns;

calculating, for only each potential candidate message, a likelihood value representing a likelihood of future engagement with the respective potential candidate message by one or more of the account holders if the respective potential candidate message was published in the requested message stream;

ranking the potential candidate messages based on the calculated likelihood values;

selecting, based on the ranking of the potential candidate messages, at least one candidate message for inclusion in the requested message stream; and

sending the requested message stream to the second account holder via the computing device, wherein the requested message stream includes the selected at least one candidate message.

14. The non-transitory computer-readable storage medium of claim 13, wherein the outstanding spend for one of the selected ad campaigns is further calculated based on a callback rate determined based on previous publications of candidate messages of the selected ad campaign to account holders of the messaging platform.

15. The non-transitory computer-readable storage medium of claim 14, wherein the callback rate is a percentage of served candidate messages that were previously presented to any account holder of the messaging platform and in response received one or more impressions from any of the account holders of the messaging platform.

16. The non-transitory computer-readable storage medium of claim 15, wherein the callback rate is a percentage of the served candidate messages that have received one or more impressions that have also received one or more engagements from any of the account holders of the messaging platform.

17. The non-transitory computer-readable storage medium of claim 15, wherein the engagement time distribution further represents a likelihood that a served candidate message that receives one or more impressions is going to receive an engagement in a specified interval of time.

18. The non-transitory computer-readable storage medium of claim 13, wherein each of the ad campaigns pay the messaging platform based on a number of engagements received by the messaging platform for the ad campaign'"'"'s published candidate messages.

19. The non-transitory computer-readable storage medium of claim 13, wherein each of the ad campaigns pay the messaging platform based on a number of engagements with candidate messages of the ad campaign that are received by the messaging platform for each of a plurality of different engagement categories, and wherein at least two of the engagement categories have different costs.

20. The non-transitory computer-readable storage medium of claim 13, wherein at least one of the selected ad campaigns has a targeting strategy selected from a group consisting of keyword targeting, account targeting, demographic targeting, lookalike targeting, recent follow targeting, temporal targeting, retargeting, production targeting, and consumption targeting.

21. The non-transitory computer-readable storage medium of claim 13, wherein the instructions for calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes instructions for modeling the likelihood of engagement based on a logistic regression analysis of a history of engagements by account holders of the messaging platform with previous candidate messages presented to the respective account holders.

22. The non-transitory computer-readable storage medium of claim 13, wherein the instructions for calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes instructions for applying machine learning to a history of engagements by the respective account holders in the one or more account holders with previous candidate messages in order to model the likelihood of engagement for each respective account holder as:

23. The non-transitory computer-readable storage medium of claim 22, wherein the instructions for applying the machine learning includes instructions for analyzing, for each respective account holder of the one or more account holders, the history of engagement by the respective account holder with previous candidate messages using logistic regression.

24. The non-transitory computer-readable storage medium of claim 13, wherein the instructions for calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes instructions for modeling, for each account holder in the one or more account holders, a likelihood of engagement with the potential candidate message via a machine learning analysis of a history of engagement by the account holder with previous candidate messages presented to the account holder.

25. A messaging platform that publishes a plurality of account holder message streams, including a message stream of a first account holder, the messaging platform comprising:

a network interface;

a processor connected to the network interface; and

a memory, wherein the memory includes program instructions that, when executed by the processor, cause the processor to;

receive a request, from a computing device associated with a second account holder of the messaging platform, for the message stream of the first account holder;

select two or more ad campaigns resident on the messaging platform, each selected ad campaign having a budget and at least one candidate message;

calculate a current spend for each of the selected ad campaigns, the current spend representing a portion of the budget already spent by the respective ad campaign;

determine an engagement time distribution by at least applying a first smoothing distribution to a first tunable parameter to generate a first product, applying a second smoothing distribution to a second tunable parameter to generate a second product, and combining the first product and the second product;

calculate an outstanding spend for each of the selected ad campaigns based on a time at which the messaging platform received the request, the engagement time distribution, account holders that received but did not yet engage with one or more candidate messages from the respective ad campaign and a predicted clickthrough rate, wherein the predicted clickthrough rate is calculated based on a features vector and a weights vector, wherein the features vector comprises values of one or more of a message feature or an account feature, and wherein the weights vector comprises weight values for each of the features in the features vector;

calculate a total outstanding spend for each of the selected ad campaigns by adding the outstanding spend of the respective ad campaign to the current spend of the respective ad campaign;

identify, as potential candidate messages, candidate messages from the selected ad campaigns with total outstanding spends that are less than the budget of their respective ad campaigns;

calculate, for only each potential candidate message, a likelihood value representing a likelihood of future engagement with the respective potential candidate message by one or more of the account holders if the respective potential candidate message was published in the requested message stream;

rank the potential candidate messages based on the calculated likelihood values;

select, based on the ranking of the potential candidate messages, at least one candidate message for inclusion in the requested message stream; and

send the requested message stream to the second account holder via the computing device, wherein the requested message stream includes the selected at least one candidate message.

26. The messaging platform of claim 25, wherein the outstanding spend for one of the selected ad campaigns is further calculated based on

a callback rate determined based on previous publications of candidate messages of the selected ad campaign to account holders of the messaging platform.

27. The messaging platform of claim 26, wherein the callback rate is a percentage of served candidate messages that were previously presented to any account holder of the messaging platform and in response received one or more impressions from any of the account holders of the messaging platform.

28. The messaging platform of claim 26, wherein the callback rate is a percentage of the served candidate messages that have received one or more impressions that have also received one or more engagements from any of the account holders of the messaging platform.

29. The messaging platform of claim 27, wherein the engagement time distribution further represents a likelihood that a served candidate message that receives one or more impressions is going to receive an engagement in a specified interval of time.

30. The messaging platform of claim 25, wherein each of the ad campaigns pays the messaging platform based on a number of engagements received by the messaging platform for the ad campaign'"'"'s published candidate messages.

31. The messaging platform of claim 25, wherein each of the ad campaigns pays the messaging platform based on a number of engagements with candidate messages of the ad campaign that are received by the messaging platform for each of a plurality of different engagement categories, and wherein at least two of the engagement categories have different costs.

32. The messaging platform of claim 25, wherein at least one of the selected ad campaigns has a targeting strategy selected from a group consisting of keyword targeting, account targeting, demographic targeting, lookalike targeting, recent follow targeting, temporal targeting, retargeting, production targeting, and consumption targeting.

33. The messaging platform of claim 25, wherein calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes modeling the likelihood of engagement based on a logistic regression analysis of a history of engagements by account holders of the messaging platform with previous candidate messages presented to respective account holders.

34. The messaging platform of claim 25, wherein calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes applying machine learning to a history of engagements by respective account holders in the one or more account holders with previous candidate messages in order to model the likelihood of engagement for each respective account holder as:

35. The messaging platform of claim 34, wherein the instructions that cause the processor to apply the machine learning includes instructions that, when executed by the processor, cause the processor to analyze, for each respective account holder of the one or more account holders, the history of engagement by the respective account holder with previous candidate messages using logistic regression.

36. The messaging platform of claim 25, wherein calculating the likelihood value for a potential candidate message representing the likelihood of future engagement with the potential candidate message by one or more of the account holders includes modeling, for each respective account holder in the one or more account holders, a likelihood of engagement with the potential candidate message via a machine learning analysis of a history of engagement by the account holder with previous candidate messages presented to the account holder.