Dynamic storage and retrieval of process graphs representative of business processes and extraction of formal process models therefrom

• US 8,676,818 B2
• Filed: 05/03/2010
• Issued: 03/18/2014
• Est. Priority Date: 05/03/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Curbera, Francisco Phelan, Keyser, Paul T., Khalaf, Rania, Lakshmanan, Geetika Tewari
• Primary Examiner(s): SYED, FARHAN M
• Application Number:
  US12/772,597
• Publication Number:
  US 20110270853A1
• Time in Patent Office: 1,415 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 computer-implemented method for modeling a process, comprising:

receiving a plurality of graphs representing a business process at a plurality of different times wherein for each graph, process steps of the business process are represented as nodes, edges connecting pairs of nodes represent transitions between process steps, and thicknesses of the edges reflect frequencies of the transitions between the process steps;

calculating a numeric value representative of graph appearance for each of the plurality of received graphs based on the nodes, edges, and edge thicknesses using a distance function that computes a measure of dissimilarity between two graphs of the plurality of graphs;

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

determining a measure of dissimilarity between the process at each of the plurality of different times and a standard version of the process based on the plurality of received graphs stored in the tree-like data structure and a standard graph representing the standard version of the process; and

generating an alert when the determined measure of dissimilarities indicate that the business process has changed beyond a predetermined level within a set period of time,

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

wherein each of the received plurality of graphs is generated by automatically parsing one or more activity log files generated in the course of executing the one or more business processes by a plurality of computerized platforms involved in executing the one or more business processes.

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

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

automatically 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; 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.

3. The computer-implemented 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 computer-implemented method of claim 1, wherein the tree-like data structure is a numeric trie data structure.

5. The computer-implemented 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.

6. The computer-implemented method of claim 1, wherein generating the alert when the determined measure of dissimilarities indicates that the business process has changed beyond the predetermined level within the set period of time includes determining when the numeric value of a particular graph deviates by an amount in excess of a predetermined threshold from a numeric value representing the standard graph.

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

8. The computer-implemented 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.

9. The computer-implemented 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.

10. A computer-implemented method for modeling a process, comprising:

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

calculating a numeric value representative of graph appearance for each of the plurality of received snapshots based on the nodes, edges, and edge thicknesses using a distance function that computes a measure of dissimilarity between two graph snapshots of the plurality of graph snapshots;

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;

determining a measure of dissimilarity between the process at each of the various instantaneous points of time and a standard version of the process based on the plurality of received snapshots stored in the tree-like data structure and a standard graph representing the standard version of the process; and

generating an alert when the determined measure of dissimilarities indicate that the dynamic business process has changed beyond a predetermined level within a set period of time,

wherein each of the received plurality of graphs is generated by automatically parsing one or more activity log files generated in the course of executing the dynamic business process by a plurality of computerized platforms involved in executing the dynamic business process.

11. The computer-implemented method of claim 10, wherein the tree-like data structure is a numeric trie data structure.

12. The computer-implemented method of claim 10, 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.

13. The computer-implemented method of claim 10, 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.

14. The computer-implemented method of claim 13, wherein the snapshot of a known state is a snapshot representing an earlier point in time than is represented by the particular snapshot.

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

a non-transitory 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 a business process at a plurality of different times wherein for each graph, process steps of the business process are represented as nodes, edges connecting pairs of nodes represent transitions between process steps, and thicknesses of the edges reflect frequencies of the transitions between the process steps;

computer readable program code configured to calculate a numeric value representative of graph appearance for each of the plurality of received graphs based on the nodes, edges, and edge thicknesses;

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;

computer readable program code configured use a distance function to determine a measure of dissimilarity between the process at each of the plurality of different times and a standard version of the process based on the plurality of received graphs stored in the tree-like data structure and a standard graph representing the standard version of the process; and

computer readable program code configured to generate an alert when the determined measure of dissimilarities indicate that the business process has changed beyond a predetermined level within a set period of time,

wherein each of the received plurality of graphs is generated by automatically parsing one or more activity log files generated in the course of executing the one or more business processes by a plurality of computerized platforms involved in executing the one or more business processes.