Granted Patent B2

US 9,529,833 · App. 14/184,270 · Granted Dec 27, 2016

Abstract

Claims (72)

1. A computer-executable method for pruning a graph, comprising:

storing in a storage device of a computer a data set comprising a plurality of data elements;

determining, by the computer, a type and strength of relationship between a data element pair in the plurality of data elements;

representing the type and strength of relationship as an edge between a vertex pair representing the data element pair in a graph;

determining a minimum graph traversal threshold associated with an input query received by the computer for the graph, wherein the minimum graph traversal threshold indicates a minimum number of traversal steps needed for the input query in the graph;

identifying that a number of traversal steps for a first connected component in the graph is greater than or equal to the minimum graph traversal threshold, and wherein a connected component includes a set of one or more vertices, which are coupled to each other via edges and are not coupled to a vertex outside of the set;

identifying that a number of traversal steps for a second connected component in the graph is smaller than the minimum graph traversal threshold;

generating a second graph comprising the first connected component by pruning the second connected component from the graph; and

processing the input query on the second graph to extract information of interest from the data set.

2. The method of claim 1 , wherein the set of one or more vertices in the connected component includes one or more of:

an isolated vertex; and

a set of vertices coupled to each other via one or more edges.

3. The method of claim 1 , wherein a respective element in the data set is stored on one or more tables in the storage device, wherein the element is identified based on a first identifier; and

wherein identifying that a number of traversal steps for the second connected component is smaller than the minimum graph traversal threshold comprises one or more tabular operations performed on the one or more tables.

4. The method of claim 3 , further comprising, in response to identifying an element in the data set not to be represented by a connected component in the graph, generating a second identifier for the element.

5. The method of claim 4 , further comprising mapping the second identifier to the first identifier in a mapping table in the storage device.

6. The method of claim 1 , further comprising:

assigning a label to a respective vertex in the graph;

propagating a label from a first vertex to a second vertex; and

identifying a set of vertices associated with the same label.

7. The method of claim 6 , wherein identifying that a number of traversal steps for the second connected component is smaller than the minimum graph traversal threshold comprises determining whether a size of the identified set of vertices is smaller than the minimum graph traversal threshold.

8. The method of claim 1 , wherein an element in the data set indicates one or more of:

a customer of a store; and

a product of the store; and

wherein the type of relationship indicates whether the customer has purchased the product.

9. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for graph pruning, comprising:

storing in a storage device of a computer a data set comprising a plurality of data elements;

determining, by the computer, a type and strength of relationship between a data element pair in the plurality of data elements;

representing the type and strength of relationship as an edge between a vertex pair representing the data element pair in a graph;

determining a minimum graph traversal threshold associated with an input query received by the computer for the graph, wherein the minimum graph traversal threshold indicates a minimum number of traversal steps needed for the input query in the graph;

identifying that a number of traversal steps for a first connected component in the graph is greater than or equal to the minimum graph traversal threshold, and wherein a connected component includes a set of one or more vertices, which are coupled to each other via edges and are not couple to a vertex outside of the set;

identifying that a number of traversal steps for a second connected component in the graph is smaller than the minimum graph traversal threshold;

generating a second graph comprising the first connected component by pruning the second connected component from the graph; and

processing the input query on the second graph to extract information of interest from the data set.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the set of one or more vertices in the connected component includes one or more of:

an isolated vertex; and

a set of vertices coupled to each other via one or more edges.

11. The non-transitory computer-readable storage medium of claim 9 , wherein a respective element in the data set is stored on one or more tables in the storage device, wherein the element is identified based on a first identifier; and

wherein identifying that a number of traversal steps for the second connected component is smaller than the minimum graph traversal threshold comprises one or more tabular operations performed on the one or more tables.

12. The non-transitory computer-readable storage medium of claim 11 , wherein the method further comprises, in response to identifying an element in the data set not to be represented by a connected component in the graph, generating a second identifier for the element.

13. The non-transitory computer-readable storage medium of claim 12 , wherein the method further comprises mapping the second identifier to the first identifier in a mapping table in the storage device.

14. The non-transitory computer-readable storage medium of claim 9 , wherein the method further comprises:

assigning a label to a respective vertex in the graph;

propagating a label from a first vertex to a second vertex; and

identifying a set of vertices associated with the same label.

15. The non-transitory computer-readable storage medium of claim 14 , wherein identifying that a number of traversal steps for the second connected component is smaller than the minimum graph traversal threshold comprises determining whether a size of the identified set of vertices is smaller than the minimum graph traversal threshold.

16. The non-transitory computer-readable storage medium of claim 9 , wherein an element in the data set indicates one or more of:

a customer of a store; and

a product of the store; and

wherein the type of relationship indicates whether the customer has purchased the product.

17. A computing system for graph pruning, the system comprising:

one or more processors;

a storage device;

a computer-readable medium coupled to the one or more processors having instructions stored thereon that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:

storing in the storage device a data set comprising a plurality of data elements;

determining, by the computing system, a type and strength of relationship between a data element pair in the plurality of data elements;

representing the type and strength of relationship as an edge between a vertex pair representing the data element pair in a graph;

determining a minimum graph traversal threshold associated with an input query received by the computer for the graph, wherein the minimum graph traversal threshold indicates a minimum number of traversal steps needed for the input query in the graph;

identifying that a number of traversal steps for a first connected component in the graph is greater than or equal to a minimum graph traversal threshold, and wherein a connected component includes a set of one or more vertices, which are couple to each other via edges and are not couple to a vertex outside of the set;

identifying that a number of traversal steps for a second connected component in the graph is smaller than the minimum graph traversal threshold;

generating a second graph comprising the first connected component by pruning the connected component from the graph; and

processing the input query on the second graph to extract information of interest from the data set.

18. The computing system of claim 17 , wherein a respective element in the data set is stored on one or more tables in the storage device, wherein the element is identified based on a first identifier; and

wherein identifying that a number of traversal steps for the second connected component is smaller than the minimum graph traversal threshold comprises one or more tabular operations performed on the one or more tables.

19. The computing system of claim 18 , wherein the operations further comprises:

in response to identifying an element in the data set not to be represented by a connected component in the graph, generating a second identifier for the element; and

mapping the second identifier to the first identifier in a mapping table in the storage device.

20. The computing system of claim 17 , wherein the operations further comprises:

assigning a label to a respective vertex in the graph;

propagating a label from a first vertex to a second vertex; and

identifying a set of vertices associated with the same label; and

wherein identifying that a number of traversal steps for the second connected components is smaller than the minimum graph traversal threshold comprises determining whether a size of the identified set of vertices is smaller than the minimum graph traversal threshold.

Assignments (10)