Database Reference
In-Depth Information
Figure 13: Data fl ow of frame metadata model agent
items that do not satisfy the minimum support threshold. The resulting set or list is denoted
L. Thus, we have L = [P1:7, P2:6, P3:6, P4:2, P5:2]. Then, the algorithm creates a tree with
a root named 'null'. Next, it scans the database again. The items in each transaction are
processed in L order and a branch is created for each transaction.
For example, the scan of the fi rst transaction, “144.214.36.101: P2, P1, P5”, contains
three visited pages (P2, P1, P5), and leads to the construction of the fi rst branch of the tree
with three nodes: <(P2:1), (P1:1), (P5:1)>, where P2 is linked as a child of the root, P1 is
linked to P2, and P5 is linked to P1. The second transaction, “144.214.36.102”, contains
the visited pages P1 and P4, which lead to the construction of the second branch with two
nodes: <(P1:1), (P4:1)>, where P1 is linked as a child of the root and P4 is linked to P1.
The third transaction, “144.214.36.103”, contains the visited pages P2, P1 and P4, which
would result in a branch where P2 is linked to the root. P1 is linked to P2, and P4 is linked
to P1. However, this branch shares a common prefi x, <P2>, with the existing path for
“144.214.36.101”. Therefore, we increment the count of the P2 node by 1, and create a new
node, (P1:1), which is linked as a child of (P2:2). Also we create another new node, (P4:1),
which is linked as a child of (P1:1). In general, when considering the branch to be added
for a transaction, the count of each node along a common prefi x is incremented by 1, and
nodes for the items following the prefi x are created and linked accordingly. The action in
reading transactions and tree construction are iterative processed until the last transaction.
The tree obtained after scanning all of the transactions is shown in Figure 11. To facilitate
tree traversal, an item header table is built so that each item points to its occurrences in the
tree via a chain of node-links. Therefore, the problem of mining frequent patterns in web log
is transformed to that of mining the FP-tree. Figure 12 shows the pseudo-code for sequential
frequent pattern growth algorithm.
