Utilization of probabilistic characteristics for reduction of graph database traversals

• US 10,402,403 B2
• Filed: 01/06/2017
• Issued: 09/03/2019
• Est. Priority Date: 12/15/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Viken Valvag, Steffen, Johansen, Amund Kronen, Eidesen, Dag Steinnes, Kvalnes, Åge, Kreutzer, Tor, Karlberg, Jan-Ove Almli, Heen, Peter Dahle
• Primary Examiner(s): Khong, Alexander
• Assistant Examiner(s): Cheung, Hubert
• Application Number:
  US15/399,975
• Publication Number:
  US 20180173760A1
• Time in Patent Office: 970 Days
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

Traversing data stored in a relational graph by utilization of probabilistic characteristics associated with the graph nodes is disclosed. When a user submits a request with a graph query, an initial node associated with the graph query is identified. Further, the edge type associated the node is extracted from the graph query. When traversing the graph by following relevant edges from the initial node to new nodes, each new node is queried with the extracted edge type. If the query for the node is negative, then the edges for the particular node are not enumerated. However, if the query for the node is positive, then the edges for the particular node are enumerated for expanding the subgraph. This process continues until the subgraph is expanded to include all relevant nodes. Thus, the computational efficiency is improved by reducing the number of edges that must be traversed when performing graph queries.

Claims

1. A computer readable storage device having a set of instructions, which when executed, performs a method for utilization of probabilistic characteristics for reduction of graph database traversals, the method comprising:

receiving a graph query at a graph server hosting a graph database, the graph database comprising a plurality of nodes connected by one or more edges;

identifying an initial node from the plurality of nodes associated with the graph query;

extracting an edge type associated with the initial node from the graph query;

querying a probabilistic characteristic of each node from the plurality of nodes that is connected to the initial node by an edge to determine whether the edge is associated with the extracted edge type;

selecting a subset of the plurality of nodes, the selected subset including each node from the plurality of nodes for which the edge was determined to be associated with the extracted edge type;

continuing performance of the graph query by examining the selected subset of the plurality of nodes; and

transmitting results of the graph query.

2. The computer readable storage device of claim 1, wherein the probabilistic characteristic of each node identifies an edge type for the edge connected to the initial node.

3. The computer readable storage device of claim 1, wherein the probabilistic characteristic of each node is stored in-line with the node in the graph database.

4. A system for utilization of probabilistic characteristics for reduction of graph database traversals, comprising:

a processing unit; and

a memory including computer readable instructions, which when executed by the processing unit, causes the system to be operable to;

receive a graph query at a graph server hosting a graph database, the graph database comprising a plurality of nodes connected by one or more edges;

identify an initial node from the plurality of nodes associated with the graph query;

extract an edge type associated with the initial node from the graph query;

query a probabilistic characteristic of each node from the plurality of nodes that is connected to the initial node by an edge to determine whether the edge is associated with the extracted edge type;

select a subset of the plurality of nodes, the selected subset including each node from the plurality of nodes for which the edge was determined to be associated with the extracted edge type;

continue performance of the graph query by examining the selected subset of the plurality of nodes; and

transmit results of the graph query.

5. The system of claim 4, wherein the probabilistic characteristic of each node identifies an edge type for the edge connected to the initial node.

6. The system of claim 4, further comprising receiving a response to querying the probabilistic characteristic of each node.

7. The system of claim 6, further comprising enumerating each of one or more edges extending from a node when the edge connecting the node to the initial node is determined to be associated with the extracted edge type.

8. The system of claim 6, further comprising skipping a node when the edge connecting the node to the initial node is determined to not be associated with the extracted edge type.

9. The system of claim 4, wherein the probabilistic characteristic of each node is stored in-line with the node in the graph database.

10. The system of claim 4, wherein the probabilistic characteristic of each node is accessed as the graph database is traversed, thereby reducing computational resource expenditures.

11. The system of claim 4, wherein the probabilistic characteristic of each node is loaded into the memory in response to the node being accessed via a query search.

12. A method for utilization of probabilistic characteristics for reduction of graph database traversals, the method comprising:

receiving a graph query at a graph server hosting a graph database, the graph database comprising a plurality of nodes connected by one or more edges;

identifying an initial node from the plurality of nodes associated with the graph query;

extracting an edge type associated with the initial node from the graph query;

querying a probabilistic characteristic of each node from the plurality of nodes that is connected to the initial node by an edge to determine whether the edge is associated with the extracted edge type;

selecting a subset of the plurality of nodes, the selected subset including each node from the plurality of nodes for which the edge was determined to be associated with the extracted edge type;

continuing performance of the graph query by examining the subset of the plurality of nodes; and

transmitting results of the graph query.

13. The method of claim 12, wherein the probabilistic characteristic of each node identifies an edge type for the edge connected to the initial node.

14. The method of claim 12, further comprising receiving a response to querying the probabilistic characteristic of each node.

15. The method of claim 14, further comprising enumerating each of one or more edges extending from a node when the edge connecting the node to the initial node is determined to be associated with the extracted edge type.

16. The method of claim 14, further comprising skipping a node when the edge connecting the node to the initial node is determined to not be associated with the extracted edge type.

17. The method of claim 12, wherein the probabilistic characteristic for each node is stored in-line with the node in the graph database.

18. The method of claim 12, wherein the probabilistic characteristic for each node is accessed as the graph database is traversed, thereby reducing computational resource expenditures.