Dynamic Storage and Retrieval of Process Graphs

• US 20110270853A1
• Filed: 05/03/2010
• Published: 11/03/2011
• Est. Priority Date: 05/03/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lakshmanan, Geetika Tewari, Khalaf, Rania, Keyser, Paul T., Curbera, Francisco
• Granted Patent: US 8,676,818 B2
• Time in Patent Office: Days
• US Class Current: 707/755
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method for modeling a process includes receiving a plurality of graphs representing processes wherein for each graph. A sequence of process steps of the processes are represented as nodes and edges connecting pairs of nodes represent transitions between process steps. A numeric value representative of graph appearance for each of the plurality of received graphs is calculated. Each of the plurality of received graphs is stored within a tree-like data structure according to its corresponding numeric value. Each of the above steps is performed using a computer system.

Claims

1. A method for modeling a process, comprising:

receiving a plurality of graphs representing processes wherein for each graph, a sequence of process steps of the processes are represented as nodes and edges connecting pairs of nodes represent transitions between process steps;

calculating a numeric value representative of graph appearance for each of the plurality of received graphs; and

storing each of the plurality of received graphs within a tree-like data structure according to its corresponding numeric value,

wherein each of the above steps is performed using a computer system.

2. The method of claim 1, wherein each of the received plurality of graphs is generated by:

collecting data pertaining to executed process steps from one or more activity log files;

parsing the collected data to determine a set of process steps that have been performed;

determining an incidence value representing how many times each performed process step follows each of the other performed process steps of the collected data;

generating a graph representing a model of the executed process by representing each process step that has been performed as a node of the graph and each transition between process steps as an edge on the graph, wherein for any given pair of nodes of the graph, the edge connecting the pair of nodes is assigned a number that depends upon the incidence value corresponding to how many times the process step represented by a first node of the pair is followed by the process step represented by a second node of the pair.

3. The method of claim 1, wherein the plurality of graphs represents snapshots of a dynamic graph at predetermined temporal intervals, at user-specified intervals, or upon satisfaction of a triggering criterion.

4. The method of claim 1, wherein the numeric values for the graphs are calculated by employing a transformation function.

5. The method of claim 4, wherein the transformation function is a distance function that computes a measure of dissimilarity between two graphs of the plurality of graphs.

6. The method of claim 1, wherein the tree-like data structure is a numeric trie data structure.

7. The method of claim 1, wherein when there are more than a predetermined number of graphs stored in a single bucket or bin of the tree-like data structure, an alert is generated.

8. The method of claim 1, wherein when the numeric value of a particular graph deviates by an amount in excess of a predetermined threshold from a numeric value representing a standard graph, an alert is generated.

9. The method of claim 1, wherein each graph includes representation of additional data in addition to nodes and edges.

10. The method of claim 1, wherein the edges of each graph are based on an incidence value representing how many times each process step follows each of the other process steps within the graphed processes.

11. The method of claim 1, wherein the edges of each graph are based on an incidence value representing a probability by which each process step follows each of the other process steps within the graphed processes.

12. A method for modeling a process, comprising:

receiving a plurality of graph snapshots representing a dynamic process at various instantaneous points in time, wherein for each snapshot, a sequence of process steps of the processes are represented as nodes and edges connecting pairs of nodes represent transitions between process steps;

calculating a numeric value representative of graph appearance for each of the plurality of received snapshots; and

storing each of the plurality of received snapshots within a tree-like data structure according to its corresponding numeric value,

wherein each of the above steps is performed using a computer system.

13. The method of claim 12, wherein the numeric value representative of graph appearance is determined for each of the acquired snapshots by employing a transformation function.

14. The method of claim 12, wherein the tree-like data structure is a numeric trie data structure.

15. The method of claim 12, wherein when there are more than a predetermined number of snapshots stored in a single bucket or bin of the tree-like data structure, an alert is generated.

16. The method of claim 12, wherein when the numeric value of a particular snapshot deviates by an amount in excess of a predetermined threshold from a numeric value representing a snapshot of a known state, an alert is generated.

17. The method of claim 16, wherein the snapshot of a known state is a snapshot representing an earlier point in time than is represented by the particular snapshot.

18. A computer program product for modeling a process, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to receive a plurality of graphs representing processes wherein for each graph, a sequence of process step of the processes are represented as nodes and edges connecting pairs of nodes represent transitions between process steps;

computer readable program code configured to calculate a numeric value representative of graph appearance for each of the plurality of received graphs; and

computer readable program code configured to store each of the plurality of received graphs within a tree-like data structure according to its corresponding numeric value.

19. A method for modeling a process, comprising:

receiving a first plurality of graphs representing processes wherein for each graph, a sequence of process steps of the processes are represented as nodes and edges connecting pairs of nodes represent transitions between process steps;

generating a first image comprising a matrix of colored elements wherein each colored element is a representation of a corresponding graph of the received first plurality of graphs and the color of each colored element is determined by calculating a color value that is dependent upon a structure of the corresponding received graph, the structure including an arrangement of nodes and edges within the graph; and

displaying the generated first image,

wherein each of the above steps is performed using a computer system.

20. The method of claim 19, wherein each of the received first plurality of graphs is generated by:

collecting data pertaining to executed process steps from one or more activity log files;

parsing the collected data to determine a set of process steps that have been performed and an incidence value representing how many times each performed process step follows each of the other performed process steps within the collected data; and

generating a graph representing a model of the executed process by representing each process step that has been performed as a node of the graph and each transition between process steps as an edge on the graph, wherein for any given pair of nodes of the graph, the edge connecting the pair of nodes is assigned a number that depends upon the incidence value corresponding to how many times the process step represented by a first node of the pair is followed by the process step represented by a second node of the pair.

21. The method of claim 19, additionally comprising:

receiving a second plurality of graphs representing processes wherein for each graph, a sequence of process step of the processes are represented as nodes and edges connecting pairs of nodes represent transitions between process steps;

generating a second image comprising a matrix of colored elements wherein each colored element is a representation of a corresponding graph of the received second plurality of graphs and the color of each colored element is determined by calculating a color value that is dependent upon a structure of the corresponding received graph, the structure including an arrangement of nodes and edges within the graph;

generating a third image comprising a matrix of colored elements wherein each colored element is a representation of a rate of change between a pixel of the first image and a corresponding pixel of the second image; and

displaying the third image.

22. The method of claim 19, wherein the first plurality of graphs represents snapshots of a dynamic graph at predetermined temporal intervals, at user-specified intervals, or upon satisfaction of a triggering criterion.

23. The method of claim 19, wherein the first plurality of graphs are stored within a tree-like data structure according to calculated numeric values representative of graph appearance.