Fast querying of social network data
First Claim
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 instead of a cluster-based query-processing system that includes multiple computers, 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;
identifying, from a stream of events associated with activity in the social network, updates to the graph that occurred subsequent to creation of the static representation;
storing, in a memory of the single computer system, a dynamic representation of the identified changes to the graph, wherein the dynamic representation comprises;
a second set of fixed-size blocks representing changes to the nodes and edges caused by the updates to the graph; and
a second index that maps a subset of the identifiers for the nodes and the edges to offsets of the second set of fixed-size blocks; and
using the dynamic representation and the static representation of the graph to process, by the single computer system, one or more queries of the graph by, for each of one or more identifiers in the query;
using the second index to match the identifier to an offset to one or more blocks in the second set of fixed-size blocks that match the query; and
when the second index does not contain the identifier, using the first index to match the identifier to an offset to one or more blocks in the first set of fixed-size blocks that match the query.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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 instead of a cluster-based query-processing system that includes multiple computers, 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; identifying, from a stream of events associated with activity in the social network, updates to the graph that occurred subsequent to creation of the static representation; storing, in a memory of the single computer system, a dynamic representation of the identified changes to the graph, wherein the dynamic representation comprises; a second set of fixed-size blocks representing changes to the nodes and edges caused by the updates to the graph; and a second index that maps a subset of the identifiers for the nodes and the edges to offsets of the second set of fixed-size blocks; and using the dynamic representation and the static representation of the graph to process, by the single computer system, one or more queries of the graph by, for each of one or more identifiers in the query; using the second index to match the identifier to an offset to one or more blocks in the second set of fixed-size blocks that match the query; and when the second index does not contain the identifier, using the first index to match the identifier to an offset to one or more blocks in the first set of fixed-size blocks that match the query. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. An apparatus, comprising:
-
a single computer system having 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; identify, from a stream of events associated with activity in the social network, updates to the graph that occurred subsequent to creation of the static representation; store, in the memory, a dynamic representation of the identified changes to the graph, wherein the dynamic representation comprises; a second set of fixed-size blocks representing changes to the nodes and edges caused by the updates to the graph; and a second index that maps a subset of the identifiers for the nodes and the edges to offsets of the second set of fixed-size blocks; and use the dynamic representation and the static representation of the graph to process one or more queries of the graph by, for each of one or more identifiers in the query; using the second index to match the identifier to an offset to one or more blocks in the second set of fixed-size blocks that match the query; and when the second index does not contain the identifier, using the first index to match the identifier to an offset to one or more blocks in the first set of fixed-size blocks that match the query. - View Dependent Claims (12, 13, 14, 15)
-
-
16. 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; identify, from a stream of events associated with activity in the social network, updates to the graph that occurred subsequent to creation of the static representation; maintain a dynamic representation of the identified changes to the graph, wherein the dynamic representation comprises; a second set of fixed-size blocks representing changes to the nodes and edges caused by the updates to the graph; and a second index that maps a subset of the identifiers for the nodes and the edges to offsets of the second 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 dynamic representation and the static representation of the graph to process one or more queries of the graph by, for each of one or more identifiers in the query; using the second index to match the identifier to an offset to one or more blocks in the second set of fixed-size blocks that match the query; and when the second index does not contain the identifier, using the first index to match the identifier to an offset to one or more blocks in the first set of fixed-size blocks that match the query. - View Dependent Claims (17, 18, 19, 20)
-
Specification