Exploration in a real time messaging platform

• US 10,692,114 B1
• Filed: 11/26/2018
• Issued: 06/23/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, Neufeld, James, Goel, Ashish, Jahr, Michael, Srivastava, Utkarsh, Pandey, Sandeep
• Primary Examiner(s): Elchanti, Tarek
• Application Number:
  US16/200,582
• Time in Patent Office: 575 Days
• Field of Search: 705 1466
• CPC Class Codes: G06Q 30/0249 based upon budgets or funds
• CPC Class Codes: G06Q 30/0269 based on user profile or attribute
• 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, by a system of one or more computing devices and from a client device of an account holder of a social media platform, a request for a message stream of messages published on the social media platform;

identifying a set of candidate messages each associated with a respective bid value;

for each candidate message in the set of candidate messages;

predicting, by the system, a respective likelihood of engagement of the account holder with the candidate message based on a number of engagements with the candidate massage, wherein the number of engagements comprises a number of times the candidate message received an engagement from other account holders of the social media platform when published in respective message stream of the other account holders, and

calculating, by the system, a rank value for the candidate message, the rank value being calculated as a function of the likelihood of engagement and the bid value of the candidate message;

determining, by the system and for each candidate message in the set of candidate messages, a respective rank of the candidate message relative to other candidate messages in the set of candidate messages, the respective rank being determined based on the calculated rank values of each candidate message;

determining, by the system, whether a rank for a particular candidate message is lower than a threshold rank;

in response to determining that the rank of the particular candidate message is lower than the threshold rank, determining, by the system, whether a number of impressions of the particular candidate message is fewer than a threshold number of impressions, wherein the number of impressions comprises a number of times the particular candidate message was published in message streams of other account holders of the social media platform, and wherein the threshold number of impressions represents a number of impressions at which the predicted likelihood of engagement is deemed to be accurate;

responsive to determining that the number of impressions for the particular candidate message is less than the threshold number of impressions;

increasing the rank value of the particular candidate message, and

replacing the rank of the particular candidate message with a new rank calculated for the particular candidate message based on the increased rank value;

selecting at least one candidate message from candidate messages in the set of candidate messages that have respective ranks greater than the threshold rank; and

sending the message stream to the client device for display, wherein the message stream includes the selected at least one candidate message.

2. The method of claim 1, further comprising:

identifying a highest rank value of the rank values of the candidate messages in the set of candidate messages,

wherein increasing the respective rank value of the particular candidate message comprises increasing the respective rank value to an amount greater than the highest rank value.

3. The method of claim 1, wherein determining the number of impressions comprises identifying a number of impressions received by the respective candidate message that have not resulted in engagements as a result of being published in message streams of account holders of the social-media platform.

4. The method of claim 1, wherein the respective bid value of a candidate message represents a cost paid per engagement to the social-media platform by an associated advertiser of the candidate message, and wherein engagements comprise interactions between account holders and messages published in message streams of the social-media platform.

5. The method of claim 1, wherein determining the respective rank value is determined based on an engagement likelihood model, wherein the method further comprises:

after sending the message stream to the computing device, receiving, from the computing device, an indication of whether the user of the computing device engaged with the selected candidate message; and

updating the engagement likelihood model based on the indication of whether the user of the computing device engaged with the selected candidate message.

6. The method of claim 1, wherein determining whether the candidate message has the number of impressions fewer than the threshold number of impressions comprises comparing the number of impressions for the particular candidate message with a sampling distribution for the particular candidate messages,

and wherein increasing the rank value of the particular candidate message comprises:

determining, based on the comparison of the number of impressions and the sampling distribution, an addend for the respective candidate message; and

increasing the respective value of the respective candidate message by the determined addend.

14. The method of claim 1, further comprising:

determining, by the system, the threshold number of impressions based on a confidence value and a minimum predicted clickthrough rate, the minimum predicted clickthrough rate indicating a minimum value at which a rank value for a candidate message enables the candidate message to be selected for inclusion in the message stream.

15. The method of claim 14, wherein determining the threshold number of impressions comprises calculating, by the system, the threshold number of impressions as a quotient of the confidence value and the minimum predicted clickthrough rate.

7. A non-transitory computer-readable storage medium comprising instructions that, when executed, cause at least one processor of a computing system to:

receive, from a client device of an account holder of a social media platform, a request for a message stream messages published on the social media platform;

identify a set of candidate messages each associated with one or more message respective features and a respective bid value;

for each candidate message in the set of candidate messages;

predict a respective likelihood of engagement of the account holder with the candidate message based on a number of engagements with the candidate massage, wherein the number of engagements comprises a number of times the candidate message received an engagement from other account holders of the social media platform when published in respective message stream of the other account holders, and

calculate a rank value for the candidate message, the rank value being calculated as a function of the likelihood of engagement and the bid value of the candidate message;

determine, for each candidate message in the set of candidate messages, a respective rank of the candidate message relative to other candidate messages in the set of candidate messages, the respective rank being determined based on the calculated rank values of each candidate message;

determine whether a rank for a particular candidate message is lower than a threshold rank;

in response to determining that the rank of the particular candidate message is lower than the threshold rank, determine whether a number of impressions of the particular candidate message is fewer than a threshold number of impressions, wherein the number of impressions comprises a number of times the particular candidate message was published in message streams of other account holders of the social media platform, and wherein the threshold number of impressions represents a number of impressions at which predicted likelihood of engagement is deemed to be accurate;

responsive to determining that the number of impressions for the particular candidate message is less than the threshold number of impressions;

increase the rank value of the particular candidate message, and

replace the rank of the particular candidate message with a new rank calculated for the particular candidate message based on the increased rank value;

select at least one candidate message from candidate messages in the set of candidate messages that have respective ranks greater than the threshold rank; and

send the message stream to the client device for display, wherein the message stream includes the selected at least one candidate message.

8. The non-transitory computer-readable storage medium of claim 7, wherein the instructions further cause the at least one processor to:

identify a highest rank value of the rank values of the candidate messages in the set of candidate messages,

wherein the instructions that cause the at least one processor to increase the respective rank value of the particular candidate message comprises instructions that cause the at least one processor to increase the value to an amount greater than the highest rank value.

9. The non-transitory computer-readable storage medium of claim 7, wherein the instructions that cause the at least one processor to determine the number of impressions comprise instructions that cause the at least one processor to identify a number of impressions received by the respective candidate message that have not resulted in engagements as a result of being published in message streams of account holders of the social-media platform.

10. The non-transitory computer-readable storage medium of claim 7, wherein the instructions that cause the at least one processor to determine whether the particular candidate message has the number of impressions fewer than the threshold number of impressions comprise instructions that cause the at least one processor to compare the number of impressions for the particular candidate message with a sampling distribution for the candidate messages,

and wherein the instructions that cause the at least one processor to increase the rank value of the particular candidate message comprise instructions that cause the at least one processor to:

determine, based on the comparison of the number of impressions and the sampling distribution, an addend for the respective candidate message; and

increase the respective value of the respective candidate message by the determined addend.

16. The non-transitory computer-readable storage medium of claim 7, wherein the instructions further cause the at least one processor to:

determine the threshold number of impressions based on a confidence value and a minimum predicted clickthrough rate, the minimum predicted clickthrough rate indicating a minimum value at which a rank value for a candidate message enables the candidate message to be selected for inclusion in the message stream.

17. The non-transitory computer-readable storage medium of claim 16, wherein the instructions that cause the at least one processor to determine the threshold number of impressions comprise instructions that cause the at least one processor to calculate the threshold number of impressions as a quotient of the confidence value and the minimum predicted clickthrough rate.

11. A system comprising:

at least one processor; and

a memory configured to store instructions that, when executed by the at least one processor, cause the at least one processor to;

receive, from a client device of an account holder of a social media platform, a request for a message stream of messages published on the social media platform;

identify a set of candidate messages each associated with a respective bid value;

for each candidate message in the set of candidate messages;

predict a respective likelihood of engagement of the account holder with the candidate message based on a number of engagements with the candidate massage, wherein the number of engagements comprises a number of times the candidate message received an engagement from other account holders of the social media platform when published in respective message stream of the other account holders, and

calculate a rank value for the candidate message, the rank value being calculated as a function of the likelihood of engagement and the bid value of the candidate message;

determine, for each candidate message in the set of candidate messages, a respective rank of the candidate message relative to other candidate messages in the set of candidate messages, the respective rank being determined based on the calculated rank values of each candidate message;

determine whether a rank for a particular candidate message is lower than a threshold rank;

in response to determining that the rank of the particular candidate message is lower than the threshold rank, determine whether a number of impressions of the particular candidate message is fewer than a threshold number of impressions, wherein the number of impressions comprises a number of times the particular candidate message was published in message streams of other account holders of the social media platform, and wherein the threshold number of impressions represents a number of impressions at which the predicted likelihood of engagement is deemed to be accurate;

responsive to determining that the number of impressions for the particular candidate message is less than the threshold number of impressions;

increase the rank value of the particular candidate message, and

replace the rank of the particular candidate message with a new rank calculated for the particular candidate message based on the increased rank value;

select at least one candidate message from candidate messages in the set of candidate messages that have respective ranks greater than the threshold rank; and

send the message stream to the client device for display, wherein the message stream includes the selected at least one candidate message.

12. The system of claim 11, wherein the instructions further cause the at least one processor to:

identify a highest rank value of the rank values of the candidate messages in the set of candidate messages,

wherein the instructions that cause the at least one processor to increase the respective value of the candidate message comprises instructions that cause the at least one processor to increase the rank value to an amount greater than the highest rank value.

13. The system of claim 11, wherein the instructions that cause the at least one processor to determine whether the particular candidate message has the number of impressions fewer than the threshold number of impressions comprise instructions that cause the at least one processor to compare the number of impressions for the particular candidate message with a sampling distribution for the candidate messages,

and wherein the instructions that cause the at least one processor to increase the rank value of the particular candidate message comprise instructions that cause the at least one processor to:

determine, based on the comparison of the number of impressions and the sampling distribution, an addend for the candidate message; and

increase the respective value of the candidate message by the determined addend.

18. The system of claim 11, wherein the instructions further cause the at least one processor to:

determine the threshold number of impressions by calculating a quotient between a confidence value and a minimum predicted clickthrough rate, the minimum predicted clickthrough rate indicating a minimum value at which a rank value for a candidate message enables the candidate message to be selected for inclusion in the message stream.

19. The system of claim 18, wherein the instructions that cause the at least one processor to determine the threshold number of impressions comprise instructions that cause the at least one processor to calculate the threshold number of impressions as a quotient of the confidence value and the minimum predicted clickthrough rate.

20. A method comprising:

receiving, from a client device of an account holder of a social media platform, a request for a message stream of messages published on the social media platform;

identifying a set of candidate messages each associated with a respective bid value;

for each candidate message in the set of candidate messages;

predicting a clickthough rate for the candidate message, the clickthrough rate representing a likelihood of engagement of the account holder with the candidate message;

determining whether the candidate message has a number of impressions fewer than a threshold number of impressions, wherein the number of impressions comprises a number of times the candidate message was published in message streams of other account holders of the social media platform,

responsive to determining that the number of impressions for the candidate message is fewer than the threshold number of impressions, including the candidate message in a first group of candidate messages, and

responsive to determining that the number of impressions for the candidate message is not fewer than the threshold number of impressions, including the candidate message in a second group of candidate messages;

for each candidate message in the first group of candidate messages, determining, based on the clickthrough rate predicted for the candidate message, the bid value of the candidate message, and the number of impressions determined for the candidate message, an inflated rank value for the candidate message;

for each candidate message in the second group of candidate messages, determining, based on the clickthrough rate predicted for the candidate message and the bid value, and independent of the number of impressions determined for the candidate message, a rank value for the candidate message;

determining, by the system and for each candidate message in the set of candidate messages, a rank of the candidate message relative to other candidate messages in the set of candidate messages, the rank being determined based on the determined rank values or the determined inflated rank values of each candidate message;

selecting at least one candidate message that has a rank value greater than a threshold rank, from the first group of candidate messages or the second group of candidate messages and based on the respective inflated rank value of each candidate message in the first group of candidate messages and the rank value of each candidate message in the second group of candidate messages; and

sending the message stream to the client device for display, wherein the message stream includes the selected at least one candidate message.

21. The method of claim 20, wherein determining the inflated rank values comprises, for each candidate message in the first group of candidate messages:

determining, based on the predicted clickthrough rate and the number of impressions determined for the candidate message, an initial rank value for the candidate message; and

inflating the initial rank value to a maximum rank value determined for the candidate messages in the second group of candidate messages to generate the inflated rank value for the candidate message.

22. The method of claim 20, wherein selecting the at least one candidate message comprises:

randomly selecting the first group of candidate messages or the second group of candidate messages; and

selecting the at least one candidate message from the randomly selected first group of candidate messages or second group of candidate messages.

23. The method of claim 22, wherein selecting the at least one candidate message comprises:

assigning, based on a predetermined tunable parameter, a first weight to the first group of candidate messages;

assigning, based on the predetermined tunable parameter, a second weight to the second group of candidate messages;

selecting the first group of candidate messages or the second group of candidate messages using the first weight and the second weight; and

selecting the at least one candidate message from the selected first group of candidate messages or second group of candidate messages.

24. The method of claim 20, wherein selecting the at least one candidate message comprises:

periodically alternating between selecting the at least one candidate message from the first group of candidate messages and selecting the at least one candidate message from the second group of candidate messages.

25. The method of claim 20, further comprising:

determining the threshold number of impressions based on a confidence value and a minimum predicted clickthrough rate, the minimum predicted clickthrough rate indicating a minimum value at which a rank value for a candidate message enables the candidate message to be selected for inclusion in the message stream.

26. The method of claim 25, wherein determining the threshold number of impressions comprises calculating the threshold number of impressions as a quotient of the confidence value and the minimum predicted clickthrough rate.

27. The method of claim 20, wherein selecting the at least one candidate message comprises:

selecting the at least one candidate message from the first group of candidate messages or from the second group of candidate messages using Thompson-fraction sampling.

28. The method of claim 20, wherein each candidate message in the set of candidate messages is associated with one or more respective message features, and wherein selecting the at least one candidate message further comprises comparing the one or more message features of the at least one candidate message to one or more account features of the account holder.