GRAPH PROCESSING SYSTEM THAT ALLOWS FLEXIBLE MANIPULATION OF EDGES AND THEIR PROPERTIES DURING GRAPH MUTATION

• US 20180315228A1
• Filed: 04/28/2017
• Published: 11/01/2018
• 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
• Granted Patent: US 10,776,966 B2
• Time in Patent Office: Days
• 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 simplify edges of a graph;

selecting and configuring a strategy subset of the plurality of configurable strategies to define a particular simplification scheme;

simplifying a graph by applying the strategy subset to the graph.

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 a subset 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 of:

minimum, maximum, sum, count, average, median, mode, or distinct.

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

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

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

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

a remote procedure call, or a declarative message.

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

extensible markup language (XML), JavaScript object notation (JSON), or 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 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 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 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.

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 simplify edges of a graph;

selecting and configuring a strategy subset of the plurality of configurable strategies to define a particular simplification scheme;

simplifying a graph by applying the strategy subset to the graph.