Utilization of probabilistic characteristics for reduction of graph database traversals

Patent metadata

Field	Value
Publication number	US-10402403-B2
Application number	US-201715399975-A
Country	US
Kind code	B2
Filing date	Jan 6, 2017
Priority date	Dec 15, 2016
Publication date	Sep 3, 2019
Grant date	Sep 3, 2019

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.

First claim

We claim:

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.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Viken Valvåg Steffen
• Johansen Amund Kronen
• Eidesen Dag Steinnes
• Kvalnes Åge
• Kreutzer Tor
• Karlberg Jan-Ove Almli
• Heen Peter Dahle

Classifications

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N5/022 Primary

  Knowledge engineering; Knowledge acquisition · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06N5/003

  Physics · mapped topic