Systems and methods for visualizing and manipulating graph databases

• US 10,713,258 B2
• Filed: 07/14/2017
• Issued: 07/14/2020
• Est. Priority Date: 07/26/2013
• Status: Active Grant

• Current Assignee: Drisk Incorporated
• Original Assignee: Drisk Incorporated
• Inventors: Stetson, Robert Chess, Aptekar, Jacob
• Primary Examiner(s): Nguyen, Cam Linh T
• Application Number:
  US15/650,776
• Publication Number:
  US 20170316059A1
• Time in Patent Office: 1,096 Days
• Field of Search: 707773, 707607, 707723, 707771, 707798
• CPC Class Codes: G06F 16/24566 Recursive queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957

Abstract

Systems and methods for visualizing and manipulating graph databases in accordance embodiments of the invention are disclosed. In one embodiment of the invention, a graph database manipulation device includes a processor and a memory configured to store a graph database manipulation application, wherein the graph database manipulation application configures the processor to obtain a graph database including a set of nodes and a set of edges, determine a source node within the set of nodes, locate a set of related nodes based on the source node and the set of edges, recursively locate a set of sub-related nodes based on the set of related nodes and the set of edges, generate a representation of the set of related nodes from the perspective of the source node, and recursively update the generated representation of the set of sub-related nodes from the perspective of the source node and the related nodes.

Claims

1. A graph database manipulation device comprising:

at least one processor;

a memory connected to the at least one processor and storing a graph database manipulation application; and

a display device in communication with the at least one processor;

wherein the graph database manipulation application directs the at least one processor to;

obtain a graph database, wherein the graph database comprises;

a set of nodes; and

a set of edges, wherein an edge in a set of edges defines a relationship between a first node in the set of nodes and a second node in the set of nodes and an edge comprises;

edge weight metadata; and

edge display metadata, wherein the edge display metadata describes the spatial relationship between the first node and the second node;

determine a source node;

generate a set of approximated nodes by partitioning the graph database into partial segments within the graph structure;

calculate a set of approximated edges between the source node and the set of approximated nodes based on the edge weight metadata and the edge display metadata;

generate an approximate view of the graph database based on the set of approximated nodes and the set of approximated edges.

2. The graph database manipulation device of claim 1, wherein the source node comprises a node in the set of nodes.

3. The graph database manipulation device of claim 1, wherein the source node comprises a node not present within the graph database virtually linked to at least one node within the graph database.

4. The graph database manipulation device of claim 1, wherein each approximated node in the set of approximated nodes represents at least one node in a region of the graph database.

5. The graph database manipulation device of claim 1, wherein a spatial cursor representing a user effector selects at least one partial segment.

6. The graph database manipulation device of claim 1, wherein the graph structure is represented in Cartesian space.

7. The graph database manipulation device of claim 1, wherein the set of approximated nodes comprises at least one node representing an aggregation of a subset of nodes in the set of nodes.

8. The graph database manipulation device of claim 1, wherein generating a set of approximated nodes comprises obtaining a random sampling of nodes in the set of nodes within a distance from the source node.

9. The graph database manipulation device of claim 1, wherein generating the set of approximated nodes comprises obtaining a sampling of nodes in the set of nodes based on the number of edges between nodes in the set of nodes and the source node.

10. The graph database manipulation device of claim 1, wherein generating the set of approximated nodes comprises analyzing metadata.

11. The graph database manipulation device of claim 10, wherein the metadata comprises priority metadata.

12. The graph database manipulation device of claim 1, wherein calculating an edge in the set of approximated edges comprises calculating the squared complex weight based on edge weight metadata.

13. The graph database manipulation device of claim 1, wherein the graph database manipulation application further directs the at least one processor to:

determine a second source node;

generate a second set of approximated nodes;

calculate a second set of approximated edges between the second source node and the second set of approximated nodes based on the edge weight metadata and the edge display metadata;

generate a second approximate view of the graph database based on the second set of approximated nodes and the second set of approximated edges.

14. The graph database manipulation device of claim 13, wherein the display switches from displaying the first approximate view of the graph database to displaying the second approximate view of the graph database.

15. The graph database manipulation device of claim 1, wherein the display is connected to the graph database manipulation device via a network.

16. The graph database manipulation device of claim 1, wherein the graph database manipulation application further directs the processor to display the approximate view of the graph database using the display device.

17. The graph database manipulation device of claim 1, wherein the graph database manipulation application further directs the processor to generate approximated edge weight metadata.

18. The graph database manipulation device of claim 1, wherein the graph database manipulation application further directs the processor to generate an approximate view of the approximated graph database.

19. The graph database manipulation device of claim 1, wherein the at least one processor comprises at least one graphics processing unit.

20. A method for manipulating a graph database comprising:

obtaining a graph database, wherein the graph database is stored on a memory connected to at least one processor, and wherein the graph database comprises;

a set of nodes; and

a set of edges, wherein an edge in a set of edges defines a relationship between a first node in the set of nodes and a second node in the set of nodes and an edge comprises;

edge weight metadata; and

edge display metadata, wherein the edge display metadata describes the spatial relationship between the first node and the second node;

determining a source node using the at least one processor;

generating a set of approximated nodes by partitioning the graph database into partial segments within the graph structure using the at least one processor;

calculating a set of approximated edges between the source node and the set of approximated nodes based on the edge weight metadata and the edge display metadata using the at least one processor.