Database Reference
In-Depth Information
ADD 1st
TRANSACTION
a,b,c,d,e
ADD 2nd
TRANSACTION
a,b,c,f,d
ADD 3rd
TRANSACTION
a,f
ADD 4th
TRANSACTION
b,f,e
ADD 5th
TRANSACTION
a,b,c,d,e
{}
{}
{}
{}
{}
a:1
a:2
a:3
a:3
b:1
a:4
b:1
b:1
b:2
b:2
f
f:1
b:2
f:1
f:1
b:3
f
f:1
f
f:1
c:1
c:2
c:2
c:2
e:1
c:3
e:1
d:1
d:1
f:1
d:1
f
d:1
f:1
d:2
f:1
e:1
e:1
d:1
e:1
d:1
e:1
d:1
e:2
d:1
ADD POINTERS
{}
a:4
b:1
b:3
f:1
f:1
c:3
e:1
d:2
f:1
e:2
d:1
Fig. 2.10
FP-Tree construction
additional overhead. This results in a different set of trade-offs as compared to the
array representation.
The initial FP-Tree is constructed as follows. We start with the empty FP-Tree
FPT
. Before constructing the FP-Tree, the database is scanned and infrequent items
are removed. The frequent items are sorted in decreasing order of support. The initial
construction of FP-Tree is straightforward, and similar to how one might insert a
string in a trie. For every insertion, the counts of the relevant nodes that are affected
by the insertion are incremented by 1. If there has been any sharing of prefix between
the current transaction
t
being inserted, and a previously inserted transaction then
t
will be in the same path until the common prefix. Beyond this common prefix,
new nodes are inserted in the tree for the remaining items in
t
, with support count
initialized to 1. The above procedure ends when all transactions have been inserted.
To store the items in the final FP-Tree, a list structure called header table is
maintained. A chain of pointers threads through the occurrence of the item in the
FP-Tree. Thus, this chain of pointers need to be constructed in addition to the trie
data structure. Each entry in this table stores the item label and pointers to the
node representing the leftmost occurrence of the item in the FP-Tree (first item in
the pointer chain). The reason for maintaining these pointers is that it is possible
to determine the conditional FP-Tree for an item by chasing the pointers for that
item. An example of the initial construction of the FP-Tree data structure from a
