Graph processing system that allows flexible manipulation of edges and their properties during graph mutation

• US 10,776,966 B2
• Filed: 04/28/2017
• Issued: 09/15/2020
• Est. Priority Date: 04/28/2017
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Boettcher, Jan, Weld, Alexander, Schmid, Korbinian, Hong, Sungpack, Chafi, Hassan
• Primary Examiner(s): Chu, David H
• Application Number:
  US15/581,820
• Publication Number:
  US 20180315228A1
• Time in Patent Office: 1,236 Days
• Field of Search: None
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

Techniques are provided for strategy-based graph simplification. In an embodiment, a computer provides configurable strategies that simplify edges of a graph. A client selects and configures a strategy subset of the configurable strategies to define a particular simplification scheme. The computer simplifies a graph by applying the strategy subset to the graph. In embodiments, predefined classes or other application programming interface (API) is provided to clients to obtain and customize strategy instances, such as with a factory or builder. Strategy instances may be imperative or declarative. A service implementation, such as a graph engine, may be embedded or remoted. Techniques herein provide for reuse and optimization.

Claims

1. A method comprising:

providing a plurality of configurable strategies that can simplify edges of property graphs that include property values of edge properties of edges;

dynamically creating a variable amount of instances, including a first strategy instance and a second strategy instance and a third strategy instance, of a same configurable strategy of the plurality of configurable strategies;

dynamically identifying a first name of a first edge property and a first threshold value to configure the first strategy instance;

dynamically identifying a second name of a second edge property and a second threshold value to configure the second strategy instance;

dynamically identifying a third name of a third edge property and a third threshold value to configure the third strategy instance, wherein the first name and the second name and the third name are distinct;

selecting and configuring a strategy subset, including said variable amount of instances, of the plurality of configurable strategies to define a particular simplification scheme;

simplifying, after said configuring said strategy subset, a property graph that comprises a plurality of edges by applying the strategy subset to the property graph;

wherein the method is performed by one or more computers.

2. The method of claim 1 wherein providing a plurality of configurable strategies comprises providing an application programming interface (API).

3. The method of claim 2 wherein providing an API comprises providing one or more factories to instantiate particular strategies of the plurality of configurable strategies.

4. The method of claim 1 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by a plurality of edges, selects multiple edges of the plurality of edges to retain.

5. The method of claim 4 wherein applying the strategy subset comprises:

applying a higher priority strategy of the strategy subset to select an initial subset of the plurality of edges;

applying a lower priority strategy of the strategy subset to select a single edge of the initial subset.

6. The method of claim 4 wherein applying the strategy subset comprises:

applying a particular strategy of the strategy subset a first time to select a first edge of the plurality of edges to remove;

applying the particular strategy a second time to select a second edge of the plurality of edges to remove.

7. The method of claim 4 wherein selects a subset of the plurality of edges comprises selects edges that originate from a first vertex and terminate at a different vertex.

8. The method of claim 1 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by a plurality of edges, merges a subset of the plurality of edges into a combined edge.

9. The method of claim 1 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by one or more edges, changes at least one edge of the one or more edges from directed to undirected.

10. The method of claim 1 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by one or more edges, applies at least one aggregation function selected from the group consisting of:

sum, count, average, median, mode, and distinct.

11. The method of claim 10 wherein the at least one aggregation function is applied for at least one selected from the group consisting of:

selecting a particular edge to retain, and selecting a particular property value of one edge of the one or more edges.

12. The method of claim 1 wherein applying the strategy subset to the property graph comprises applying the strategy subset to create a new property graph.

13. The method of claim 1 further comprising sending the strategy subset to a remote server that hosts the property graph using at least one selected from the group consisting of:

a remote procedure call, and a declarative message.

14. The method of claim 13 wherein sending the strategy subset to the remote server comprises sending at least one selected from the group consisting of:

extensible markup language (XML), JavaScript object notation (JSON), and a serialized object-oriented instance.

15. The method of claim 1 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by one or more edges, applies a user-defined function.

16. The method of claim 1 wherein selecting and configuring a strategy subset comprises sub-classing at least one of the plurality of configurable strategies.

17. The method of claim 1 wherein the strategy subset comprises a strategy that removes at least one property of an edge.

18. The method of claim 1 wherein:

the edges of the property graph are stored in an array;

edges that originate from a same vertex are stored contiguously within the array.

19. The method of claim 1 wherein an implementation of a strategy of the plurality of configurable strategies accesses, within a data structure that encodes an edge, a property of the edge by using none of:

multi-level indirection, auto-boxing, unboxing, or control-flow branching.

20. The method of claim 1 further comprising reusing the strategy subset by applying the strategy subset to a second property graph.

21. The method of claim 1 wherein applying the strategy subset comprises applying multiple subsets of the plurality of configurable strategies.

22. The method of claim 1 wherein an implementation of a strategy of the plurality of configurable strategies uses a method reference to access, within a data structure that encodes an edge, a property of the edge by using none of:

multi-level indirection, auto-boxing, unboxing, or control-flow branching.

23. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:

providing a plurality of configurable strategies that can simplify edges of property graphs that include property values of edge properties of edges;

dynamically creating a variable amount of instances, including a first strategy instance and a second strategy instance and a third strategy instance, of a same configurable strategy of the plurality of configurable strategies;

dynamically identifying a first name of a first edge property and a first threshold value to configure the first strategy instance;

dynamically identifying a second name of a second edge property and a second threshold value to configure the second strategy instance;

dynamically identifying a third name of a third edge property and a third threshold value to configure the third strategy instance, wherein the first name and the second name and the third name are distinct;

selecting and configuring a strategy subset, including said variable amount of instances, of the plurality of configurable strategies to define a particular simplification scheme;

simplifying, after said configuring said strategy subset, a property graph that comprises a plurality of edges by applying the strategy subset to the property graph.

24. The one or more non-transitory computer-readable media of claim 23 wherein providing a plurality of configurable strategies comprises providing an application programming interface (API).

25. The one or more non-transitory computer-readable media of claim 24 wherein providing an API comprises providing one or more factories to instantiate particular strategies of the plurality of configurable strategies.

26. The one or more non-transitory computer-readable media of claim 23 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by a plurality of edges, selects multiple edges of the plurality of edges to retain.

27. The one or more non-transitory computer-readable media of claim 26 wherein applying the strategy subset comprises:

applying a higher priority strategy of the strategy subset to select an initial subset of the plurality of edges;

applying a lower priority strategy of the strategy subset to select a single edge of the initial subset.

28. The one or more non-transitory computer-readable media of claim 26 wherein applying the strategy subset comprises:

applying a particular strategy of the strategy subset a first time to select a first edge of the plurality of edges to remove;

applying the particular strategy a second time to select a second edge of the plurality of edges to remove.

29. The one or more non-transitory computer-readable media of claim 26 wherein selects a subset of the plurality of edges comprises selects edges that originate from a first vertex and terminate at a different vertex.

30. The one or more non-transitory computer-readable media of claim 23 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by a plurality of edges, merges a subset of the plurality of edges into a combined edge.

31. The one or more non-transitory computer-readable media of claim 23 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by one or more edges, changes at least one edge of the one or more edges from directed to undirected.

32. The one or more non-transitory computer-readable media of claim 23 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by one or more edges, applies at least one aggregation function selected from the group consisting of:

sum, count, average, median, mode, and distinct.

33. The one or more non-transitory computer-readable media of claim 32 wherein the instructions further cause the at least one aggregation function to be applied for at least one selected from the group consisting of:

selecting a particular edge to retain, and selecting a particular property value of one edge of the one or more edges.

34. The one or more non-transitory computer-readable media of claim 23 wherein applying the strategy subset to the property graph comprises applying the strategy subset to create a new property graph.

35. The one or more non-transitory computer-readable media of claim 23 wherein the instructions further cause sending the strategy subset to a remote server that hosts the property graph using at least one selected from the group consisting of:

a remote procedure call, and a declarative message.

36. The one or more non-transitory computer-readable media of claim 35 wherein sending the strategy subset to the remote server comprises sending at least one selected from the group consisting of:

extensible markup language (XML), JavaScript object notation (JSON), and a serialized object-oriented instance.

37. The one or more non-transitory computer-readable media of claim 23 wherein the plurality of configurable strategies comprises a strategy that, for each pair of vertices connected by one or more edges, applies a user-defined function.

38. The one or more non-transitory computer-readable media of claim 23 wherein selecting and configuring a strategy subset comprises sub-classing at least one of the plurality of configurable strategies.

39. The one or more non-transitory computer-readable media of claim 23 wherein the strategy subset comprises a strategy that removes at least one property of an edge.

40. The one or more non-transitory computer-readable media of claim 23 wherein the instructions further cause:

the edges of the property graph to be stored in an array;

edges that originate from a same vertex to be stored contiguously within the array.

41. The one or more non-transitory computer-readable media of claim 23 wherein an implementation of a strategy of the plurality of configurable strategies is configured to access, within a data structure that encodes an edge, a property of the edge by using none of:

multi-level indirection, auto-boxing, unboxing, or control-flow branching.

42. The one or more non-transitory computer-readable media of claim 23 wherein the instructions further cause reusing the strategy subset by applying the strategy subset to a second property graph.

43. The one or more non-transitory computer-readable media of claim 23 wherein applying the strategy subset comprises applying multiple subsets of the plurality of configurable strategies.

44. The one or more non-transitory computer-readable media of claim 23 wherein an implementation of a strategy of the plurality of configurable strategies is configured to use a method reference to access, within a data structure that encodes an edge, a property of the edge by using none of:

multi-level indirection, auto-boxing, unboxing, or control- flow branching.