Database Reference
In-Depth Information
Fig. 9.1
Closed enumerate
tree example [
23
]
Several works [
19
,
20
,
39
,
49
] have also mined for the exact set of CFIs with
a sliding window. CFI-STREAM [
39
] maintains a tree (DIU-tree) which records all
closed itemsets, without prejudging whether they are frequent or not. For this reason,
CFI-STREAM has two advantages: (1) It can respond to queries for any support
threshold
θ
, and (2) its performance is independent of
θ
. It outperforms MOMENT
when the support threshold is low. GC-TREE [
19
] exploits closure generators and a
total lexicographic ordering among all itemsets in order to compute closure more
efficiently. Each node in the tree is a 3-tuple:
, where
gen
is the
closure generator,
eitem
is the item used to extend
gen
to another closed itemset,
and
clo
is the closed itemset. In NEWMOMENT, each item's history of occurrence is
recorded as a
w
-bit binary vector, where
w
is the window width. Each time a new
transaction arrives, one simply pushes a new bit to the front and drops a bit from
the back. Bit sequences are computed for itemsets as well as items, and the itemset
histories are linked to each itemset in the frequent itemset tree. This enables more
efficient updates of support levels. As a consequence, NEWMOMENT runs faster and
uses less memory that MOMENT.
Cheng et al. [
20
] have introduced the notion of
semi-FCIs
, which progressively
increase the support threshold for an itemset as it resides in the window longer, to
efficiently compute an estimated set of CFIs. Furthermore, they use an inverted index
instead of a prefix tree to record semi-FCIs.
While most works have used the sliding window model, Liu et al. contribute FP-
CDS [
59
], which addresses the landmark window model, and Gupta et al. propose
CLICI [
31
], which uses the damped window model. Like LOSSY COUNTING, FP-
CDS uses batch processing and may produce false positive results within an error
threshold. CLICI uses a lattice rather than a tree structure. The lattice records all
closed itemsets, similar to FCI-STREAM.
gen
,
eitem
,
clo
