Database Reference
In-Depth Information
Item
f
Expected support
4.9
( f :0.7):[3,1,3]
( g :0.6):[0,2,0]
g
6.6
h
3.0
i
1.5
( g :0.9):[2,1,3]
( h :0.7):[1,0,1]
( h :0.8):[1,0,1]
( i :0.5):[0,0,1]
( i :0.5):[1,0,1]
Fig. 14.8 The SUF-tree for streaming uncertain data D 3
counts (representing the newest streaming data). The SUF-tree is constructed in a
similar fashion as the construction of the UF-tree, except that the occurrence count
is inserted as the newest entry in the list of occurrence counts. Figure 14.8 shows an
example of a SUF-tree constructed from the streaming uncertain data in Table 14.7 .
Once the SUF-tree is constructed, it is always kept up-to-date when the window
slides. As the window continues to slide in the dynamic streams, SUF-growth delays
the mining of frequent patterns from uncertain streaming data until the user requests
for the patterns. At that time, SUF-growth mines the up-to-dated SUF-tree in a fashion
similar to UF-growth with the user-specified minsup to find all frequent patterns.
8.2
UF-streaming for the Sliding Window Model
Besides the SUF-growth algorithm, Leung and Hao [ 36 ] also extended the UF-
growth algorithm to produce an approximate algorithm called UF-streaming . Unlike
SUF-growth (which is an exact algorithm but uses a “delayed” mining mode), UF-
streaming is an approximate algorithm that uses an “immediate” mining mode.
Specifically, for every incoming batch of streaming uncertain data, UF-streaming
applies UF-growth (ref. Sect. 5.1) to that batch with a preMinsup threshold (where
preMinsup < minsup ) to find “frequent” patterns (or more precisely, sub-frequent
or potentially frequent patterns due to the use of the preMinsup threshold). These
“frequent” patterns having expected support
preMinsup are then stored in a tree
structure called UF-stream . Each tree path represents a “frequent” pattern. Each
tree node stores a list of w expected support values (one for each batch), where the
i -th value indicates the expected support of that “frequent” pattern in the i -th batch.
When a new batch flows in, the window slides, and the algorithm shifts the w ex-
pected support values of each node in the UF-stream structure so as to ensure that
it always captures the “frequent” patterns mined from the w most recent batches of
streaming uncertain data. Figure 14.9 shows an example of a UF-stream structure
Search WWH ::




Custom Search