Information Technology Reference
In-Depth Information
12.6.5
Distributed mining algorithm of association rules
Here we first introduce distributed mining algorithm FDM-LP which is a FDM
with local pruning, including candidate set reduction and local pruning.
Algorithm 12.6
FDM-LP algorithm(Cheung, Han et al, 1996).
Input: DB
i
(
i
=1,…,
n
), the database partition at each site
S
i
Output: L, all global large data sets
Method:
1. if k = 1 then
2.
T
i
(1)
= get_local_count(DB
i
,∅,1)
3. else {
4.
CG
(
k
)
=
n
i
G
CG
i
(
k
)
=
n
i
G
Apriori_gen(
GL
i
(
k
-1)
);
5.
T
i
(
k
)
= get_local_count(DB
i
,
CG
(
k
)
,
i
);}
6. for_all
X
∈
T
i
(
k
)
do
7. If
X
.
sup
i
²
s
×
D
i
then
8. for
j
= 1 to
n
do
9. if polling_site(
X
) =
S
j
then
insert <
X
,
X.sup
i
> into
LL
i,j
(
k
)
;
10. for
j
= 1,…,
n
do send
LL
i,
j(
k
)
to site
S
j
;
11. for
j
= 1,…,
n
do {
12. receive
LL
j,i
(k)
;
13. for_all
X
∈
LL
j,i
(
k
)
do {
14. if
X
∉
LP
i
(
k
)
then
insert
X
into
LP
i
(
k
)
;
15. update
X
.
large_sites
; }}
16. for_all
X
∈
LP
i
(
k
)
do
17. send_polling_request(
X
);
18. reply_polling_request(
T
i
(
k
)
);
19. for_all
X
∈
LP
i
(
k
)
do {