Indexing and data storage for realtime and contemporaneous content suggestions

Patent metadata

Field	Value
Publication number	US-10599656-B1
Application number	US-201715451390-A
Country	US
Kind code	B1
Filing date	Mar 6, 2017
Priority date	Mar 4, 2016
Publication date	Mar 24, 2020
Grant date	Mar 24, 2020

Abstract

The present invention relates generally to messaging platforms, and relates more particularly to data storage such that random sampling can be accomplished in real-time in messaging platforms. Aspects of the present invention include storing a bipartite graph with associations of two node types. The graph can be stored as a power law graph. The graph can be used to provide real-time content recommendations in a messaging platform. The content recommendations can be provided using random sampling of the node types stored in the graph.

First claim

The invention claimed is:

1. A server device, comprising:
at least one computer processor comprising one or more processor cores;
a memory storing:
a plurality of segments, wherein each segment of the plurality of segments comprises a corresponding postings list of at least a first content type for users of a messaging platform, wherein each corresponding postings list for each segment of the plurality of segments corresponds to content occurring in the messaging platform during a particular time period, and wherein each corresponding postings list for each segment of the plurality of segments comprises a plurality of shards; and
a node information index comprising an indication of, for each user, an index to each shard of the corresponding postings list for each of the plurality of segments;

a search module executing on the computer processor to enable the computer processor to:
receive a query identifying a first user of the users of the messaging platform;
identify, from one or more postings lists, a random sample of the first content type for the first user, wherein identifying the random sample comprises using a corresponding index to each shard of the one or more of the postings lists to randomly sample the first content type; and
provide the random sample in response to the query; and

a recommendation engine executing on the at least one computer processor to enable the at least one computer processor to:
use the provided random sample of the first content type to provide a recommendation to the first user.

2. The server device of claim 1 wherein the at least one computer processor further comprises:
a memory writer executing on a first processor core; and
a plurality of memory readers executing on a plurality of processor cores.

3. The server device of claim 1 wherein the at least one computer processor further comprises a plurality of memory writers, each memory writer associated with a segment representing a time period, wherein a plurality of segments represent the same time period.

4. The server device of claim 1 wherein the at least one computer processor implements random sampling using a plurality of two-step random walks originating from a group of second users of the messaging platform identified in the node information index.

5. The server device of claim 1 wherein the random sampling occurs in O(1) time.

6. The server device of claim 1 wherein the recommendation engine executing on the at least one computer processor further enables the at least one computer processor to:
send the query identifying the first user of the users of the messaging platform to the search module; and
receive the random sample of the first content type for the first user.

7. The server device of claim 1 further comprising a frontend module executing on the at least one computer processor to enable to the at least one computer processor to:
receive a request for a recommendation; and
request a recommendation from the messaging platform.

8. A method for providing recommendations in a messaging platform, comprising:
maintaining a graph associating user information and content information on the messaging platform;
storing the user information and the content information in a plurality of segments, wherein each segment of the plurality of segments comprises a partition of the graph of user information and content information occurring on the messaging platform during a particular time period and wherein corresponding content information and corresponding user information of each segment comprises a plurality of shards, each shard having different storage properties;
indexing each segment of the plurality of segments according to each user in user information stored in the segment being indexed such that an index to each shard associated with content information stored in the segment being indexed is created;
receiving a query identifying a first user of the messaging platform;
identifying a random sample of particular content information for the identified first user, wherein identifying the random sample comprises using corresponding indexes to corresponding shards to randomly sample the particular content information for the identified first user of the messaging platform;
providing the random sample in response to the query; and
using the provided random sample to provide a recommendation to the first user.

9. The method of claim 8 further comprising:
sending a query identifying the first user of the users of the messaging platform; and
receiving the random sample of the first content information for the first user.

10. The method of claim 8 wherein the random sampling occurs in O(1) time.

11. The method of claim 8 further comprising writing to a segment representing a time period, wherein a plurality of segments represent the same time period.

12. The method of claim 8 further comprising:
receiving a request for a recommendation; and
requesting a recommendation from the messaging platform.

13. The method of claim 8 further comprising implementing random sampling using a plurality of two-step random walks originating from a group of second users of the messaging platform identified in the index.

14. The method of claim 8 further comprising:
executing a memory writer on a first processor core; and
executing a plurality of memory readers on a plurality of processor cores.

15. The method of claim 8 , wherein the recommendation comprises one or more of recommended message content or recommended users of the messaging platform.

16. A non-transitory computer readable medium or media comprising one or more sequences of instructions which, when executed by one or more processors, causes steps for directing traffic in a data communication system comprising:
maintaining a graph associating user information and content information on a messaging platform;
storing the user information and the content information in a plurality of segments, wherein each segment of the plurality of segments comprises a partition of the graph of user information and content information occurring on the messaging platform during a particular time period and wherein corresponding content information and corresponding user information of each segment comprises a plurality of shards, each shard having different storage properties;
indexing each segment of the plurality of segments according to each user in user information stored in the segment being indexed such that an index to each shard associated with content information stored in the segment being indexed is created;
receiving a query identifying a first user of the messaging platform;
identifying a random sample of particular content information for the identified first user, wherein identifying the random sample comprises using corresponding indexes to corresponding shards to randomly sample the particular content information for the identified first user of the messaging platform;
providing the random sample in response to the query; and
using the provided random sample to provide a recommendation to the first user.

17. The computer readable medium of claim 16 wherein the random sampling occurs in O(1) time.

18. The computer readable medium of claim 16 further comprising instructions for:
receiving a request for a recommendation; and
requesting a recommendation from the messaging platform.

19. The computer readable medium of claim 16 , further comprising instruction for implementing random sampling using a plurality of two-step random walks origina

Assignees

• Twitter Inc

Inventors

• Sharma Aneesh
• Jiang Jerry

Classifications

• G06F16/9535

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/2457 Primary

  with adaptation to user needs · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2228 Primary

  Indexing structures · CPC title