Methods, systems, and computer program products for storing graph-oriented data on a column-oriented database

• US 9,576,020 B1
• Filed: 10/18/2012
• Issued: 02/21/2017
• Est. Priority Date: 10/18/2012
• Status: Active Grant

• Current Assignee: Proofpoint Incorporated
• Original Assignee: Proofpoint Incorporated
• Inventors: Patterson, Justin
• Primary Examiner(s): Uddin, Md. I
• Application Number:
  US13/655,183
• Time in Patent Office: 1,587 Days
• Field of Search: 707/705, 707/706, 707/722, 707/741, 707/798, 707/E17.037
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Systems, methods, and computer program products for efficiently storing and accessing graph-oriented information retrieved from disparate sources using an interface that effectively emulates a graph database to access a set of indexed, column-oriented tables. One embodiment is a system that includes a server and a plurality of storage nodes. The server retrieves graph-oriented social networking data for multiple users, identifies vertices, edges and associated properties within the data and stores this information in key-value lookup tables within a column-oriented database. The server can receive graph-oriented queries, convert the graph-oriented query to corresponding key-value lookup queries, and search the tables of the column-oriented database using the key-value lookup queries. The results of the lookup queries can be converted to a graph-oriented representation and presented to a user.

Claims

1. A system for maintaining and accessing a graph-oriented data set over a network, the system comprising:

a server communicatively connected to the network; and

a plurality of column-oriented storage nodes coupled to the server via the network;

wherein the server is configured to, for each user of a plurality of users;

store social networking data associated with the each user on one or more of the plurality of column-oriented storage nodes,

maintain a graph model of the social networking data associated with the each user,

wherein the graph model identifies a plurality of vertices and a plurality of edges defined by the social networking data associated with the each user,

wherein the graph model works cooperatively with a column-oriented database to store, for each vertex and each edge in the graph model, one or more corresponding entries in one or more of a plurality of lookup tables in the plurality of column-oriented storage nodes,

the column-oriented database comprising a vertex key-value table and an edge key-value table,

the vertex key-value table configured for storing entities identified in the social networking data associated with the each user,

the edge key-value table configured for storing relationships identified in the social networking data associated with the each user,

receive a graph-oriented query via a user input interface on a computing device communicatively connected to the server via the network,

analyze the graph-oriented query and sequentially convert the graph-oriented query to one or more column-oriented key-value lookup queries,

search the plurality of lookup tables distributed across the plurality of column-oriented storage nodes by performing the column-oriented key-value lookup queries corresponding to the graph-oriented query on the plurality of column-oriented storage nodes, wherein the plurality of column-oriented storage nodes are physically separate storage nodes, and

convert results from the search to a graph model representation and present on the computing device to a user via the network.

2. The system of claim 1, wherein the server is configured to analyze the results from searching the plurality of lookup tables distributed across the plurality of column-oriented storage nodes.

3. The system of claim 1, wherein the server is configured to search the plurality of lookup tables distributed across the plurality of column-oriented storage nodes in response to receiving the graph-oriented query.

4. The system of claim 1, wherein the column-oriented key-value lookup queries are restricted by one or more identifiers associated with a user that submits the graph-oriented query to the server and wherein the results from the search include only entries that are associated with the one or more identifiers associated with the user.

5. The system of claim 1, wherein each of the entries is stored with a customer identifier and a user account identifier.

6. The system of claim 1, wherein the server is configured to access a plurality of social networking web sites and to retrieve one or more components of the social networking data from each of the social networking web sites, wherein for each component of the one or more components of the social networking data, the server identifies corresponding vertices and edges in the each component, and stores the identified vertices and edges in one or more of the plurality of lookup tables.

7. The system of claim 1, wherein the server is configured to search the one or more of the plurality of lookup tables by performing at least a first one of the column-oriented key-value lookup queries on a first one of the plurality of lookup tables which is stored on a first one of the plurality of column-oriented storage nodes and performing at least a second one of the column-oriented key-value lookup queries on a second one of the plurality of lookup tables which is stored on a second one of the plurality of column-oriented storage nodes.

8. A method for maintaining and accessing a graph-oriented data set over a network, the method comprising:

storing, by a server computer communicatively connected to the network, social networking data associated with a user on one or more column-oriented storage nodes coupled to the server via the network;

maintaining, by the server computer, a graph model of the social networking data associated with the user,

wherein the graph model identifies a plurality of vertices and a plurality of edges defined by the social networking data associated with the user,

wherein the graph model works cooperatively with a column-oriented database to store, for each vertex and each edge in the graph model, one or more corresponding entries in one or more of a plurality of lookup tables in the column-oriented storage nodes,

the column-oriented database comprising a vertex key-value table and an edge key-value table,

the vertex key-value table configured for storing entities identified in the social networking data associated with the each user,

the edge key-value table configured for storing relationships identified in the social networking data associated with the each user;

receiving, by the server computer, a graph-oriented query via a user input interface on a computing device communicatively connected to the server computer via the network;

analyzing, by the server computer, the graph-oriented query and sequentially converting, by the server computer, the graph-oriented query to one or more column-oriented key-value lookup queries;

searching, by the server computer, the plurality of lookup tables distributed across the column-oriented storage nodes by performing the column-oriented key-value lookup queries corresponding to the graph-oriented query on the plurality of column-oriented storage nodes, wherein the column-oriented storage nodes are physically separate storage nodes; and

converting, by the server computer, results from the search to a graph model representation and presenting on the computing device to a user via the network.

9. The method of claim 8, further comprising analyzing the results from searching the plurality of lookup tables distributed across the column-oriented storage nodes.

10. The method of claim 8, further comprising restricting the column-oriented key-value lookup queries to entries that are associated with one or more identifiers associated with a user that submits the graph-oriented query to the server computer.

11. The method of claim 8, wherein each of the entries is stored with a customer identifier and a user account identifier.

12. The method of claim 8, further comprising accessing a plurality of social networking web sites and retrieving one or more components of the social networking data from each of the social networking web sites, wherein for each component of the one or more components of the social networking data, the server computer identifies corresponding vertices and edges in the each component, and stores the identified vertices and edges in one or more of the plurality of lookup tables.

13. The method of claim 8, wherein searching the plurality of lookup tables comprises performing at least a first one of the column-oriented key-value lookup queries on a first one of the plurality of lookup tables which is stored on a first one of the column-oriented storage nodes and performing at least a second one of the column-oriented key-value lookup queries on a second one of the plurality of lookup tables which is stored on a second, physically separate one of the column-oriented storage nodes.

14. A computer program product comprising at least one non-transitory computer readable storage medium containing computer instructions configured to cause a computer system to perform:

storing social networking data associated with a user on one or more column-oriented storage nodes, the storage nodes communicatively coupled to the computer system via the network;

maintaining a graph model of the social networking data associated with the user,

wherein the graph model identifies a plurality of vertices and a plurality of edges defined by the social networking data associated with the user,

wherein the graph model works cooperatively with a column-oriented database to store, for each vertex and each edge in the graph model, one or more corresponding entries in one or more of a plurality of lookup tables in the column-oriented storage nodes,

the column-oriented database comprising a vertex key-value table and an edge key-value table,

the vertex key-value table configured for storing entities identified in the social networking data associated with the each user,

the edge key-value table configured for storing relationships identified in the social networking data associated with the each user;

receiving a graph-oriented query via a user input interface on a computing device communicatively connected to the computer system via the network;

analyzing the graph-oriented query and sequentially converting the graph-oriented query to one or more column-oriented key-value lookup queries;

searching the plurality of lookup tables distributed across the column-oriented storage nodes by performing the column-oriented key-value lookup queries corresponding to the graph-oriented query on the plurality of column-oriented storage nodes, wherein the column-oriented storage nodes are physically separate storage nodes; and

converting results from the search to a graph model representation and presenting on the computing device to a user via the network.

15. The computer program product of claim 14, wherein the computer instructions further cause the computer system to perform:

analyzing the results from searching the plurality of lookup tables distributed across the column-oriented storage nodes.

16. The computer program product of claim 14, wherein the computer instructions further cause the computer system to perform:

accessing a plurality of social networking web sites and retrieving one or more components of the social networking data from each of the social networking web sites, wherein for each component of the one or more components of the social networking data, the computer system identifies corresponding vertices and edges in the each component, and stores the identified vertices and edges in one or more of the plurality of lookup tables.

17. The computer program product of claim 14, wherein searching the plurality of lookup tables comprises performing at least a first one of the column-oriented key-value lookup queries on a first one of the plurality of lookup tables which is stored on a first one of the column-oriented storage nodes and performing at least a second one of the column-oriented key-value lookup queries on a second one of the plurality of lookup tables which is stored on a second, physically separate one of the column-oriented storage nodes.

18. The computer program product of claim 14, wherein the computer instructions further cause the computer system to perform:

restricting the column-oriented key-value lookup queries to entries that are associated with one or more identifiers associated with a user that submits the graph-oriented query to the computer system.