Utilization of probabilistic characteristics for reduction of graph database traversals
First 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3)
-
-
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. - View Dependent Claims (5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17, 18)
-
Specification