Unidirectional lookalike campaigns in a messaging platform

• US 9,361,322 B1
• Filed: 03/14/2014
• Issued: 06/07/2016
• Est. Priority Date: 03/15/2013
• Status: Expired due to Fees

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: Twitter Inc (X Holdings Corp.)
• Inventors: Dutta, Chinmoy, Li, Junjun, Rastogi, Vibhor, Lu, Wanchen, Pandey, Sandeep, Srivastava, Utkarsh
• Primary Examiner(s): Jami, Hares
• Application Number:
  US14/214,455
• Time in Patent Office: 816 Days
• Field of Search: 707/722, 707/733, 707/734, 707/749
• US Class Current: 1/1
• 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:

accessing a unidirectional connection graph storing unidirectional connections between account holders of a messaging platform, each account holder associated with a message stream including messages they have authored as well as messages authored by other account holders whose message streams they are subscribed to receive, each account holder associated via unidirectional connections with a plurality of other account holders who have subscribed to receive their message stream;

receiving a request for a list of similar account holders who have subscribers similar to subscribers of a requested account holder;

identifying a list of subscribing account holders of the requested account holder using the unidirectional connection graph;

identifying a set of candidate account holders that the subscribing account holders subscribe to;

determining a degree of similarity between each of the candidate account holders and the requested account holder based on the subscribing account holders of the requested account holders and the subscribers of each of the candidate account holders;

selecting a subset of similar account holders based on the degrees of similarity of the candidate account holders; and

providing the subset of similar account holders responsive to the request.

2. The method of claim 1, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between the subscribing account holders and the subscribers of the candidate account holder.

3. The method of claim 1, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between account features of the candidate account holder, and account features of the requested account holder.

4. The method of claim 3, wherein the features of the candidate account holder and the features of the requested account holder are determined based on features of messages published in the message streams of the candidate account holder and the requested account holder, respectively.

5. The method of claim 3, wherein the features of the candidate account holder and the features of the requested account holder are determined based on features of messages published in the message streams of the candidate account holder and the requested account holder and which are authored by the candidate account holder or requested account holder, respectively.

6. The method of claim 3, wherein the features of the candidate account holder and the features of the requested account holder are determined based on engagements by the candidate account holder and the requested account holder, respectively, on messages in the messaging platform.

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

accessing a unidirectional connection graph storing unidirectional connections between account holders of a messaging platform, each account holder associated with a message stream including messages they have authored as well as messages authored by other account holders whose message streams they are subscribed to receive, each account holder associated via unidirectional connections with a plurality of other account holders who have subscribed to receive their message stream;

receiving a request for a list of similar account holders who have subscribers similar to subscribers of a requested account holder;

identifying a list of subscribing account holders of the requested account holder using the unidirectional connection graph;

identifying a set of candidate account holders that the subscribing account holders subscribe to;

determining a degree of similarity between each of the candidate account holders and the requested account holder based on the subscribing account holders of the requested account holders and the subscribers of each of the candidate account holders;

selecting a subset of similar account holders based on the degrees of similarity of the candidate account holders; and

providing the subset of similar account holders responsive to the request.

15. The non-transitory computer-readable storage medium of claim 7, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between the subscribing account holders and the subscribers of the candidate account holder.

16. The non-transitory computer-readable storage medium of claim 7, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between account features of the candidate account holder, and account features of the requested account holder.

17. The non-transitory computer-readable storage medium of claim 16, wherein the features of the candidate account holder and the features of the requested account holder are determined based on features of messages published in the message streams of the candidate account holder and the requested account holder, respectively.

8. A method comprising:

accessing a unidirectional connection graph storing unidirectional connections between account holders of a messaging platform, each account holder associated with a message stream including messages they have authored as well as messages authored by other account holders whose message streams they are subscribed to receive, each account holder associated via unidirectional connections with a plurality of other account holders who have subscribed to receive their message stream;

receiving a request for a list of similar account holders who subscribe to other account holders similar to account holders a requested account holder subscribes to;

identifying a list of account holders the requested account holder subscribes to using the unidirectional connection graph;

identifying a set of candidate account holders that the list of account holders subscribe to;

determining a degree of similarity between each of the candidate account holders and the requested account holder based on the list of account holders and the accounts each of the candidate account holders subscribes to;

selecting a subset of similar account holders based on the degrees of similarity of the candidate account holders; and

providing the subset of similar account holders responsive to the request.

9. The method of claim 8, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between the list of account holders and the accounts the candidate account holder subscribes to.

10. The method of claim 8, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between account features of the candidate account holder, and account features of the requested account holder.

11. The method of claim 10, wherein the features of the candidate account holder and the features of the requested account holder are determined based on features of messages published in the message streams of the candidate account holder and the requested account holder, respectively.

12. The method of claim 10, wherein the features of the candidate account holder and the features of the requested account holder are determined based on features of messages published in the message streams of the candidate account holder and the requested account holder and which are authored by the candidate account holder or requested account holder, respectively.

13. The method of claim 10, wherein the features of the candidate account holder and the features of the requested account holder are determined based on engagements by the candidate account holder and the requested account holder, respectively, on messages in the messaging platform.

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

accessing a unidirectional connection graph storing unidirectional connections between account holders of a messaging platform, each account holder associated with a message stream including messages they have authored as well as messages authored by other account holders whose message streams they are subscribed to receive, each account holder associated via unidirectional connections with a plurality of other account holders who have subscribed to receive their message stream;

receiving a request for a list of similar account holders who subscribe to other account holders similar to account holders a requested account holder subscribes to;

identifying a list of account holders the requested account holder subscribes to using the unidirectional connection graph;

identifying a set of candidate account holders that the list of account holders subscribe to;

determining a degree of similarity between each of the candidate account holders and the requested account holder based on the list of account holders and the accounts each of the candidate account holders subscribes to;

selecting a subset of similar account holders based on the degrees of similarity of the candidate account holders; and

providing the subset of similar account holders responsive to the request.

18. The non-transitory computer-readable storage medium of claim 14, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between the list of account holders and the accounts the candidate account holder subscribes to.

19. The non-transitory computer-readable storage medium of claim 14, wherein the degree of similarity between one of the candidate account holders and the requested account holder is determined based on cosine similarity between account features of the candidate account holder, and account features of the requested account holder.

20. The non-transitory computer-readable storage medium of claim 19, wherein the features of the candidate account holder and the features of the requested account holder are determined based on features of messages published in the message streams of the candidate account holder and the requested account holder, respectively.