Database Reference
In-Depth Information
{
f
}:[2.1,0,2.1]
{
g
}:[1.8,2.1,2.7]
{
h
}:[1.5,0,1.5]
{
i
}:[0,0,1.0]
{
f,g
}:[1.26,0,1.89]
{
f,h
}:[1.05,0,1.05]
{
g,h
}:[1.35,0,1.35]
{
g,i
}:[0,0,0.90]
{
f,g,h
}:[0.945,0,0.945]
Fig. 14.9
The UF-stream structure for streaming uncertain data
D
3
constructed for the streaming uncertain data in Table
14.7
with
preMinsup
= 0.9
<
1.0 =
minsup
.
As UF-streaming uses
preMinsup
, the UF-stream structure may contain some
false positives (i.e., every pattern
Y
having
preMinsup
expSup
(
Y
,
D
w
)
< minsup
,
where
D
w
represents the streaming uncertain data in the current sliding window) in
addition to all truly frequent patterns (i.e., every pattern
X
having
expSup
(
X
,
D
w
)
≤
≥
minsup
). At the time when the user requests for frequent patterns from uncertain
streaming data, UF-streaming traverses the UF-stream structure and returns only
those truly frequent patterns.
8.3
TUF-streaming for the Time-Fading Model
Besides the sliding window model (used by both SUF-growth and UF-streaming),
there are also other stream processing models such as time-fading and landmark mod-
els. Leung and Jiang [
38
] proposed the
TUF-streaming
algorithm to mine frequent
patterns from probabilistic datasets of uncertain data in a fashion similar to UF-
streaming, except that TUF-streaming uses the
time-fading model
instead of the slid-
ing window model. When using the time-fading model, TUF-streaming puts heavier
weights on recent batches of streaming uncertain data than older batches. Specifi-
cally, like UF-streaming, the TUF-streaming algorithm also uses the “immediate”
mining mode to apply UF-growth (ref. Sect. 5.1) to every incoming batch of stream-
ing uncertain data with a
preMinsup
threshold to find “frequent” patterns from that
batch. When using the time-fading model, the corresponding
TUF-stream
structure
(i) captures all “frequent” patterns mined from all batches but weights recent batches
heavier than older batches (i.e., monotonically decreasing weights from recent to
older data). See Fig.
14.10
, in which
α
(where 0
<α
1) is a time-fading factor.
While TUF-streaming handles batches of streaming uncertain data that come in
order, there are situations where batches may get delayed and thus arrived out of
the desired order. To deal with these situations, Jiang and Leung [
26
] extended the
TUF-streaming algorithm to mine frequent patterns from these delayed batches when
using the time-fading model.
≤
