Information Technology Reference
In-Depth Information
graph when large event logs are considered as the number of nodes is equal to
the number of messages in the log. Moreover, processing such a graph for process
discovery can be computationally expensive.
We propose in this paper a novel approach to e
ciently discover and evalu-
ate all CCs from large event logs by using message indexation and aggregation
and build an Aggregated Correlation Graph (ACG). The objective is that the
ACG graph aggregates and exhibits all the sequences of message correlations
(described using their corresponding CCs) identified in a service interaction log
using a size-ecient single graph. We define such ACG as follows:
Definition 2 (Aggregated Correlation Graph (ACG)).
We define the
ACG graph as a weighted and oriented graph in which nodes and edges have
the following properties and notations:
-
Nodes properties:
Every node is associated with a set of messages. The
set of nodes of the ACG is noted N
(
ACG
)
.
-
Edges properties:
Every edge is associated with a set of message correla-
tions. The set of edges of the ACG is noted Ed
(
ACG
)
.Anedgeisoriented
and links two nodes. Two nodes can be linked with at most one edge. If two
nodes n
1
, n
2
∈
N
(
ACG
)
are linked with an edge e
∈
Ed
(
ACG
)
,wenote
ed
(
n
1
,n
2
)=
n
1
n
2
and we say n
1
is correlated to n
2
. The weight W
(
e
)
of
an edge e
∈
Ed
(
ACG
)
is equal to the number of event correlations associated
to it.
-
Constraints on message-node association:
Every message in the log is
associated with one single node in the ACG. Two correlated messages cannot
be associated with the same node in the ACG.
-
Constraints on message correlation-edge association:
All message
correlations associated to the same edge share the same correlation condition.
Such a correlation condition is noted CCond
(
ed
)
for an edge ed
Ed
(
ACG
)
.
Every correlation of two messages is associated with one single edge in the
ACG.
∈
Root node:
-
The ACG contains necessary one default node called root node
where any message m
j
≺
/
m
j
≪
is placed if
m
m
m
.
i
i
i
In the Aggregated Correlation Graph, each node corresponds to a set of messages
and each edge represents correlations between all pairs of messages in the two
sets of messages
1
. The edge's weight represents the number of pairs of correlated
messages in the two sets of messages contained in its source and destination
nodes. The edge's type corresponds to their CC, ensuring that all correlations
represented by the same edge have the same CC.
The correlations of messages are represented in the ACG graph using oriented
edges mainly for two reasons. Firstly, time is important in correlation discovery
as if a message
m
1
is correlated with a message
m
2
and
m
1
≺
m
2
,theedge
representing such a correlation would be oriented in consequence (from the node
containing
m
1
to the node containing
m
2
). The second reason is that the ACG
1
Only binary correlations are represented (correlations of pairs of messages).
