Biology Reference
In-Depth Information
if
K does not exist
then
Compute
Child
(
K
);
Enqueue
K
to
Q
;
end if
Identify
K
as a successor of
C
;
end if
end for
end while
8.4.2.
Implementation
The efficiency of the algorithm depends on the efficient implementation of pro-
cessing a concept that include three procedures: (1) computing
Child
(); (2)testing
if an attribute set is closed; (3) testing if a concept already exists.
First, we describe how to compute
Child
(
obj
(
X
)
,X
) in
O
(
a∈
obj(
X
)
|
nbr
(
a
)
|
)
time, using a procedure, called S
PROUT
, described in the following lemma.
,ittakes
O
(
a∈
obj(
X
)
|
nbr
(
a
)
Lemma 8.1.
Fo r
(
obj
(
X
)
,X
)
∈B
|
)
to compute
Child
(
obj
(
X
)
,X
)
.
Proof.
∈
res
(
X
),weas-
sociate it with a set
E
i
(which is initialized as an empty set).
Let
res
(
X
)=
∪
a∈
obj(
X
)
nbr
(
a
)
\
X
.
For each
i
For each object
a
∈
obj
(
X
), we scan through each attribute
i
in its neighbor list
nbr
(
a
), append
a
to the set
E
i
. This step takes
O
(
a∈
obj(
X
)
|
nbr
(
a
)
|
). Next we collect all the
. We use a trie to group the same object set: search
E
i
in
the trie; if not found, insert
E
i
into the trie with
{
E
i
:
i
∈
res
(
X
)
}
sets
as its attribute set, otherwise
we append
i
to
E
i
's existing attribute set. This step takes
O
(
i∈
res(
X
)
|
{
i
}
)=
O
(
a∈
obj(
X
)
|
nbr
(
a
)
|
). Thus, this procedure, called S
PROUT
(
obj
(
X
)
,X
), takes
E
i
|
O
(
a∈
obj(
X
)
|
nbr
(
a
)
|
) time to compute
Child
(
obj
(
X
)
,X
).
∈
AttrChild
(
X
),wetestif
XS
is closed based on the second charac-
terization in Proposition 8.3. For this method to work, it requires processing the
children
Child
(
obj
(
X
)
,X
) in the decreasing order of their object-set size. Sup-
pose
AttrChild
(
X
)=
For
S
{
S
1
,...,S
k
}
|
obj
(
XS
1
)
|≥|
obj
(
XS
2
)
|≥
...
≥
where
|
obj
(
XS
k
)
. We process
S
i−
1
before
S
i
.If
XS
i−
1
is closed, we also compute its
children
Child
(
obj
(
XS
i−
1
)
,XS
i−
1
). Now to test if
XS
i
is closed, we we com-
pare
|
is not
smaller, then
XS
i
is closed otherwise it is not. To efficiently search
obj
(
XS
i
),we
use a trie (with hashing over each node) to store the object sets of concepts gener-
ated so far and it takes linear time to search and insert (if not exists) an object set.
|XS
i
|
against the size of the existing attribute set of
obj
(
XS
i
).If
|XS
i
|
Search WWH ::
Custom Search