Information Technology Reference
In-Depth Information
Algorithm 1.
Building the ACG graph
Require:
M
as the event stream sorted by time
Ensure:
Building the Aggregated Correlation Graph of all messages in
M
1:
for all
m
∈
M
do
2:
if
∃
n
∈
N
(
ACG
) such that
n
Ed
(
ACG
),
ed
=
n
∀
∈
N
(
ACG
)
/ ∃
ed
∈
n
,
n
(
n
≪
m
and
CCond
(
ed
)=
CCond
,
m
)
and
∀
n
n
∈
N
(
ACG
)
/
≪
m
,
ed
=
n
n
and
CCond
(
n
∃
ed
∈
Ed
(
ACG
)
/
,
m
)=
CCond
(
ed
)
then
3:
m
is associated with
n
n
n
4:
for all
∈
N
(
ACG
)
/
≪
m
do
(
n
5:
W
The weight of the edge between the two nodes is increased as a new
correlation has been associated to it.
}
n
)) + +
{
6:
end for
7:
else if
∃
cn
∈
N
(
ACG
)
/
cn
≪
m
then
8:
Create a new node
n
in
N
(
ACG
)
n
n
9:
∈
N
(
ACG
)
/
≪
for all
m
do
Add a new edge
n
10:
n
to
Ed
(
ACG
)
Initialize the weight of
n
11:
n
to 1
{
This is because only one correlation is associated
to it so far.
}
12:
end for
13:
else
14:
m
is associated with
root
which is the root node of the ACG.
{
The event is not correlated
to any existing node
}
15:
end if
16:
end for
3.4
Using Inverted Indexes for Ecient Message-Node Association
Inverted indexes are widely used in database systems to eciently locate in-
formation [12]. For example, an inverted index for a collection of documents is
a data structure that stores, for each term (word) occurring in the collection,
information about the locations where it occurs. Such inverted indexes allow to
make the location of items more ecient. In the following, we justify the need
and we describe the use of inverted indexes in the proposed approach to ensure
an e
cient identification of nodes associated to a given message.
Correlating messages is based on the equality of their attribute's values.
Therefore, creating an inverted index of attribute's values of all messages in
the log is an obvious solution to make correlation identification more ecient.
Having such an inverted index of values, every value refers to all its couples of
message/attribute having the same value. The inverted index can be formalized
as a function
InvInd
mapping values to couples of attributes and messages:
InvInd
:
V
−→
P
(
A
,
M
)
such that
∀
v
∈
V
,
∀
m
i
∈
M
,
∀
a
j
∈
A
,if
V
(
a
,
m
)=
v
,then(
a
,
m
)
⊂
InvInd
(
v
).
j
i
j
i
However, building the inverted index
InvInd
concerns all couples of messages
and attributes of the log and makes parsing/updating the index inecient when
large logs are used. Moreover, such an inverted index is helpful to build a corre-
lation graph of the entire event log instead of an aggregated correlation graph.
