Information Technology Reference
In-Depth Information
(7.1) if
D
i
then
Alone update of FDM-LUP algorithm is that append upper bound pruning
(line 7.1). Function g_upper_bound computes upper bound for each candidate
itemsets. In other words, g-upper-bound returns an upper bound of X as the sum:
g_upper_bound
(
X
)≥
s
×
n
=
Σ
1
X.sup
i
+
maxsup
j
X
j
j
≠
i
X
.sup
i
was computed in the process of local pruning, and maxsup
j
(
X
)
j
-1)-st iteration. If
upper bound is a smaller number than global minsup, it is used to prune
=1,…,
n
,
j
≠
i
can be computed by local support count after (
k
.
Comparing with FDM-LP algorithm, FDMLUP should usually have a smaller
number of candidate sets for count exchange.
X
Algorithm 12.8
FDM-LPP, FDM algorithm of local and poll address pruning
Method: The program fragment of FDM-LPP is obtained from Algorithm 12.6
by replacing its line 17 with the following two lines.
(16.1) if
p_upper_bound
(
X
)≥
s
×
D
i
then
(17)
end_polling_request
(
X
);
FDM-LPP algorithm appends a new step, which is polling site pruning. In this
step, polling site
S
i
accepts requests from other sites to perform polling. Each
requestes includes local large itemset
X
and its local support count
X
.sup
j
.
S
j
is
site from which delivers itemset
.large_sites is the set of all
the originating sites from which the requests for polling
X
to
S
i
,. Note that
X
X
are being sent to the
polling site (line 15). For every site
S
j
∈
X
.large_sites, the local support count
X
.sup
j
has been delivered to
S
i
. For a site
S
∉
X
.large_sites, because
X
in
S
q
is not
q
locally large,
X
.sup
q
is smaller than
s
×
D
q
. X.sup
q
is bounded by the value
min(maxsup
q
(
X
),
s
×
D
q
-1
). Therefore, an upper bound of
X
.sup
q
can be computed
by following formula:
n
Ã
Ã
(12.7)
X sup
.
+
min(
maxsup
(
X
),
s
*
D
−
1)
j
a
q
j
∈
X l
. arg
e
_
Sites
q
=
1,
q
≠
X l
. arg
e
_
sites
In FDM-LPP algorithm,
S
i
uses function
p
_upper_bound and above formula,
to compute upper bound for
.sup. This upper bound will be pruned, when it
issmaller than global support count.
X