FAST QUERYING OF SOCIAL NETWORK DATA

• US 20160314220A1
• Filed: 04/27/2015
• Published: 10/27/2016
• Est. Priority Date: 04/27/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: LinkedIn Corporation (Microsoft Corporation)
• Inventors: Jan, Jane Alam, Sachdev, Sanjay, Cho, SungJu
• Granted Patent: US 10,037,388 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/86 Mapping to a database
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9038 Presentation of query results

Abstract

The disclosed embodiments provide a system for processing data. During operation, the system obtains a graph of a social network, wherein the graph includes a set of nodes representing users in the social network and a set of edges representing relationships between pairs of the users. Next, the system stores, on a single computer system, a static representation of the graph, wherein the static representation includes a first set of fixed-size blocks representing the nodes and the edges and a first index that maps a set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks. The system then uses the static representation of the graph to process, by the single computer system, one or more queries of the graph.

Claims

1. A method for processing data, comprising:

obtaining a graph of a social network, wherein the graph comprises;

a set of nodes representing users in the social network; and

a set of edges representing relationships between pairs of the users;

storing, on a single computer system, a static representation of the graph, wherein the static representation comprises;

a first set of fixed-size blocks representing the nodes and the edges; and

a first index that maps a set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks; and

using the static representation of the graph to process, by the single computer system, one or more queries of the graph.

2. The method of claim 1, further comprising:

maintaining, in a memory of the single computer system, a dynamic representation of changes made to the graph since the creation of the static representation; and

using the dynamic representation and the static representation to process the one or more queries of the graph.

3. The method of claim 2, wherein using the dynamic representation and the static representation to process the one or more queries of the graph comprises:

searching the dynamic representation for a subset of the graph that matches a query;

when the subset of the graph is found in the dynamic representation, providing the subset of the graph from the dynamic representation in response to the query;

when the subset of the graph is not found in the dynamic representation, providing the subset of the graph from the static representation in response to the query.

4. The method of claim 2, wherein the dynamic representation of changes to the graph comprises:

a second set of fixed-size blocks representing changes to the nodes and the edges; and

a second index that maps a subset of the identifiers for the nodes and the edges to the second set of fixed-size blocks.

5. The method of claim 2, further comprising:

storing the dynamic representation in one or more files on the single computer system prior to a restart of the single computer system; and

after the restart, loading the dynamic representation from the one or more files into the memory.

6. The method of claim 2, further comprising:

periodically merging the dynamic representation into the static representation.

7. The method of claim 2, further comprising:

obtaining a new version of the graph;

updating the static representation of the graph with the new version; and

discarding the dynamic representation after the static representation is updated.

8. The method of claim 1, wherein the first set of fixed-size blocks comprises a subset of contiguous fixed-size blocks associated with active users in the social network.

9. The method of claim 1, wherein the graph is obtained as a snapshot from a primary data store.

10. The method of claim 1, wherein at least a portion of the static representation of the graph is stored in one or more solid-state drives (SSDs) in the single computer system.

11. The method of claim 1, wherein a fixed-size block in the first set of fixed-size blocks comprises:

an adjacency list of a set of edges from a node to other nodes in the graph; and

one or more attributes associated with the set of edges.

12. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

obtain a graph of a social network, wherein the graph comprises;

a set of nodes representing users in the social network; and

a set of edges representing relationships between pairs of the users;

store a static representation of the graph, wherein the static representation comprises;

a first set of fixed-size blocks representing the nodes and the edges; and

a first index that maps a first set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks; and

use the static representation of the graph to process one or more queries of the graph.

13. The apparatus of claim 12, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

maintain, in the memory, a dynamic representation of changes made to the graph since the creation of the static representation; and

using the dynamic representation and the static representation to process the one or more queries of the graph.

14. The apparatus of claim 13, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

storing the dynamic representation in one or more files on the single computer system prior to restarting the apparatus; and

after the apparatus has restarted, loading the dynamic representation from the one or more files into the memory.

15. The apparatus of claim 13, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

periodically merge the dynamic representation into the static representation.

16. The apparatus of claim 13, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

obtain a new version of the graph;

update the static representation of the graph with the new version; and

discard the dynamic representation after the static representation is updated.

17. The apparatus of claim 12, wherein the first set of fixed-size blocks comprises a subset of contiguous fixed-size blocks associated with active users in the social network.

18. A system, comprising:

a management non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to;

obtain a graph of a social network, wherein the graph comprises;

a set of nodes representing users in the social network; and

a set of edges representing relationships between pairs of the users; and

store a static representation of the graph, wherein the static representation comprises;

a first set of fixed-size blocks representing the nodes and the edges; and

a first index that maps a set of identifiers for the nodes and the edges to offsets of the first set of fixed-size blocks; and

a query-processing non-transitory computer-readable medium comprising instructions that, when executed by one or more processors, cause the system to use the static representation of the graph to process one or more queries of the graph.

19. The system of claim 18,

wherein the management non-transitory computer-readable medium further comprises instructions that, when executed by the one or more processors, cause the system to maintain, in memory, a dynamic representation of changes made to the graph since the creation of the static representation, and

wherein the query-processing non-transitory computer-readable medium further comprises instructions that, when executed by the one or more processors, cause the system to use the dynamic representation and the static representation to process the one or more queries of the graph.

20. The system of claim 18, wherein a fixed-size block in the first set of fixed-size blocks comprises:

an adjacency list of a set of edges from a node to other nodes in the graph; and

one or more attributes associated with the set of edges.