Information Technology Reference
In-Depth Information
12.6.4
Count polling
In general, few candidate itemsets are locally large at all the sites. Therefore, the
FDM algorithm will usually require much less than O(
2
) messages for
computing each candidate itemset. To ensure that FDM requires only O(
n
)
messages for every candidate itemset in all the cases, a count polling technique is
introduced.
This technology uses an assignment function to the candidate itemset
n
X
,
which acts on
's Hash function that maps X to a polling site (Suppose that this
function can be quoted in any sites). There is no relation to
X
X
's polling site and
the sites of
X
being locally large. The polling site of each candidate itemset
X
is
used to compute if
X
is globally large. To realize the purpose, corresponding
X
's
polling site should broadcast
's polling request toward all the other sites, and
collect local support counts, and compute global support counts. Because there is
only one polling site for each candidate item
X
X
, the number of
X
's total exchange
information can be reduced to O(
).
At the k-th iteration, after the pruning phase, (both local and global pruning),
has been completed, FDM uses the following procedure at each site S
i
to do the
count polling.
(1) Send candidate sets to polling sites: At site
n
S
i
, find out candidate elements of
belonging to set
LL
i
and polling site
S
j
for each polling site
S
j
, which will be
k
stored in
LL
i,j
(k)
(That is, store candidate elements according to group of their
polling site). Each local support count of candidate itemsets also is stored in
corresponding
LL
i,
j(k)
. Send each
LL
i,j
(k)
to the corresponding polling site
S
j
.
(2) Poll and collect support count: if
S
i
is a polling site,
S
i
will receive all
LL
i,j
(k)
from other sites.
S
i
firstly find out original address l
ist
, whose
X
is sent, for each
candidate itemset
, then broadcast polling request to other sites, which is not in
the original site list, to collect support count.
(3) Compute global large itemsets:
X
S
i
accepts support count from other sites, and
computes global support count for each candidate elements, then find out
globally large itemsets. Eventually,
S
i
broadcasts gl-large itemsets with their
global support count to other sites.
