Cache efficiency by social graph data ordering

Patent metadata

Field	Value
Publication number	US-10025867-B2
Application number	US-201514869656-A
Country	US
Kind code	B2
Filing date	Sep 29, 2015
Priority date	Sep 29, 2015
Publication date	Jul 17, 2018
Grant date	Jul 17, 2018

Abstract

Embodiments are disclosed for improving cache or memory efficiency of a social network system. A method according to some embodiments includes steps of: receiving an instruction to improve cache or memory efficiency of social graph data of a social graph; generating based on the social graph a partitioning tree including multiple bottom-level buckets, the partitioning tree dividing the vertices of the social graph into the bottom-level buckets and ordering the bottom-level buckets such that a social network metric regarding the vertices is optimized; assigning user IDs to the vertices of the social network in a numerical sequence based on the ordering of the bottom-level buckets; storing the social graph data of the users in storage locations in an order according to the numeral sequence of the assigned user IDs of the vertices.

First claim

We claim:

1. A method for improving storage efficiency of a social network system, comprising:
receiving an instruction to improve cache or memory efficiency of social graph data of a social graph, wherein the social graph includes multiple vertices representing social network users and some of the social network users are friends in a social network;
generating, based on the social graph, a partitioning tree including multiple bottom-level buckets, the partitioning tree dividing the vertices of the social graph into the bottom-level buckets and ordering the bottom-level buckets such that a social network metric corresponding to the vertices is optimized;
assigning user identities (IDs) to the vertices of the social network in a numerical sequence based on the ordering of the bottom-level buckets;
storing the social graph data of the users in storage locations in a storage device in an order according to the numeral sequence of the assigned user IDs of the vertices; and
responding to a social graph data request for a list of requested users by retrieving social graph data of the requested users together from storage locations that are close to each other in the storage device, wherein the requested users are related users who have been assigned the user IDs that are close to each other.

2. The method of claim 1 , wherein the partitioning tree divides the vertices of the social graph into the bottom-level buckets and orders the bottom-level buckets such that a log cost of the vertices of the social graph is minimized, the log cost being the social network metric.

3. The method of claim 2 , wherein at least some of vertices representing friend users are in the same bucket among the bottom-level buckets corresponding to the minimized log cost of the vertices of the social graph.

4. The method of claim 1 , wherein the partitioning tree divides the vertices of the social graph into the bottom-level buckets and orders the bottom-level buckets such that a log gap cost of the vertices of the social graph is minimized, the log gap cost being the social network metric.

5. The method of claim 4 , wherein vertices representing friends of a particular user tend to stay in the same bucket among the bottom-level buckets corresponding to the minimized log gap cost of the vertices of the social graph.

6. The method of claim 1 , wherein the social graph data of the vertices are stored in blocks of storage devices, and wherein the size of the bottom-level blocks of the partitioning tree is substantially equal to or less than a block size of the blocks of the storage devices.

7. The method of claim 6 , wherein said retrieving social graph data comprises:
retrieving social graph data of the requested users together from storage locations that are close to each other, wherein the social graph data of at least two of the requested users are stored in a common block of one of the storage devices.

8. The method of claim 1 , wherein said assigning user IDs to the vertices of the social network comprises:
assigning alternative user IDs to the vertices of the social network in a numerical sequence based on the ordering of the bottom-level buckets;
wherein the alternative user IDs are different from original user IDs that are assigned to the social network users when accounts of the social network users are created, the original user IDs having no relevance or correlation with relationships between vertices of the social graph.

9. The method of claim 1 , wherein said generating based on the social graph a partitioning tree comprises:
recursively dividing the social graph into buckets of vertices such that the social network metric regarding the vertices is optimized, the buckets being nodes of the partitioning tree;
determining that bottom-level buckets of the partitioning tree reach a desired level of granularity; and
stopping further divisions of the social graph.

10. The method of claim 9 , wherein the partitioning tree is a binary partitioning tree, and the nodes of the binary partitioning tree have two branches respectively.

11. The method of claim 1 , further comprising:
swapping two buckets that are child nodes of a common parent node of the partitioning tree such that the social network metric regarding the vertices is further optimized.

12. The method of claim 1 , wherein the social network metric regarding the vertices is calculated by sampling a number of representative vertices from the buckets of the social graph.

13. The method of claim 1 , further comprising:
identifying a sub-optimal vertex that falls into a first bucket based on a sub-optimal decision; and
moving the sub-optimal vertex into a second bucket so that the social network metric regarding the vertices is further optimized;
wherein the first and second buckets belong to a section led by a common ancestor node within a predetermined number of levels.

14. The method of claim 1 , further comprising:
receiving an instruction to add a new vertex representing a new user to the social graph;
adding the new vertex to a last bucket of the bottom-level buckets of the partitioning tree;
re-generating a new partitioning tree using the bottom-level buckets including the new vertex as initialization; and
assigning new user IDs to the vertices of the social network in a numerical sequence based on the ordering of the bottom-level buckets of the new partitioning tree.

15. A non-transitory machine-readable storage medium comprising a program containing a set of instructions for causing a machine to execute procedures for improving data compression efficiency of a social network system, the procedures comprising:
receiving an instruction to improve data compression efficiency of social graph data of a social graph, the social graph including multiple vertices representing social network users, some of the social network users are friends in a social network;
generating based on the social graph a partitioning tree including multiple bottom-level buckets, the partitioning tree dividing the vertices of the social graph into the bottom-level buckets and ordering the bottom-level buckets such that a social network metric regarding the vertices is optimized;
assigning user IDs to the vertices of the social network in a numerical sequence based on the ordering of the bottom-level buckets; and
storing the social graph data of the users in storage locations in an order according to the numeral sequence of the assigned user IDs of the vertices, wherein the social graph data of the users are stored in a form of differences between the social graph data of respective users and the social graph data of neighboring users.

16. The non-transitory machine-readable storage medium of claim 15 , wherein a respective user and a neighboring user are friends in the social network, and the storage space taken by the respective user is less because the difference between the social graph data of the respective user and the social graph data of the neighboring user is small.

17. The non-transitory machine-readable storage medium of claim 15 , further comprising:
responding to a social graph data request for a list of requested users by retrieving social graph data of the requested users together from storage locations that are close to each other, wherein the requested users are related users who have been assigned the user IDs that are close to each other.

18. The non-transitory machine-readable storage medium of claim 15 , wherein the partitioning tree divides the vertices of the social graph into the bottom-level buckets

Assignees

• Facebook Inc

Inventors

• Kabiljo Igor
• Dhulipala Laxman
• Shalita Alon Michael
• Sharma Arun Dattaram
• Karrer Brian Christopher

Classifications

• G06F16/955

  using information identifiers, e.g. uniform resource locators [URL] · CPC title

• G06F16/9024

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

• G06F16/24578

  using ranking · CPC title

• G06F16/9535 Primary

  Search customisation based on user profiles and personalisation · CPC title

• G06F16/278 Primary

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title