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
Search WWH ::




Custom Search