Database Reference
In-Depth Information
Table 9.3
Algorithms for frequent itemset mining of streaming data
Publication
Window
a
Batch?
Accuracy
Algorithm/(D)ata structure
All itemsets
Manku'02 [
61
]
L
b
False +
Lossy counting
Chang'03 [
14
]
D
False +
Estdec
Cheung'03 [
21
]
L
Exact
FELINE, CATS(D)
Giannella'03 [
28
]
T
b
False +
FP-stream(D)
Li'04 [
52
]
L
b
False +
DSM-FI, IsFI-Forest(D)
Yu'04 [
77
]
L
b
False
−
FPDM
Jin'05 [
40
]
S
b
False +
StreamMining
Lin'05 [
58
]
S
b
False
±
PFP
Calders'07 [
13
]
A
Exact
Raissi'07 [
70
]
T
b
False +
FIDS
Li'08 [
55
]
L
b
False +
DSM-FI
Ng'08 [
67
]
L
b
False +
CLCA
Li'09 [
49
]
S
Exact
MFI-transSW
Tanbeer'09 [
71
]
S,L,D
b
Exact
CPS-Tree(D)
Closed itemsets
Chi'04 [
23
]
S
Exact
MOMENT
Jiang'06 [
39
]
S
Exact
CLI-Stream
Chen'07 [
19
]
S
exact
GC-Tree(D)
Cheng'08 [
20
]
S
False +
IncMine
Li'09 [
56
]
S
Exact
NewMoment
Liu'09 [
59
]
L
b
False +
FP-CLS
Gupta'10 [
31
]
D
Exact
CLICI
Maximal itemsets
Lee'05 [
45
]
L,D
False
±
estDec+, Cp-Tree(D)
Li'05 [
53
]
L,S
b
False +
DSM-MSI, SFO-Forest(D)
Mao'07 [
63
]
L
Exact
INSTANT
Li'11 [
50
]
L
b
False
−
FNMFIMoDS
Li'12 [
57
]
L
Exact
INSTANT+, FP-FOREST(D)
Frequent itemsets from uncertain data
Leung'09 [
46
]
S
b
Exact w.r.t.
expected supp.
SUF-Growth
Leung'11 [
47
,
48
]
D,L
b
False +
TUF-Streaming
Hewa'12 [
34
]
L or D
b
False +
UHS-Stream, TFUHS-Stream
Top-K frequent itemsets
Wong'06 [
74
]
L,S
b
False
±
Patnaik'13 [
68
]
±
a
L
landmark,
S
sliding window,
D
damped,
T
tilted time window,
A
all types
S
b
False
Tables
9.3
list a representative set of algorithms which have been proposed for
mining frequent itemsets. The table is subdivided into five sections, each for a differ-
ent category of pattern or data: (1) general itemsets, (2) closed itemsets, (3) maximal
itemsets, (4) itemsets with uncertain data, and (5) top-K itemsets. The Window col-
umn indicates what type of window is supported: (L)andmark, (S)liding, (D)amped,
(T)ilted time, or (A)ll. If the Batch column is marked, then a key step of the algorithm
requires that transactions be processed in batches; unmarked columns indicate algo-
rithms that can update after each individual transaction. The Accuracy column tells
