Data Mining: Hash Tree based support counting

Hash tree is a very quick way to search an item. When there are many itemsets, hash tree could be used to find out if a given itemset has got required support count. But, how do we construct hash tree? The links I came across were very abstarct to define the hash tree implementation.

Suppose we want to insert (i.e. hash)

the following 3-itemsets into the tree

(9,3,6)

(8,7,1)

We have taken hashing function h(x) = N mod 3. This has three possible values for h(x) = {0, 1, 2}. Each value is a branch of a Hash tree node. So, each node will have three branches.

Now, lets insert Itemsets = {8, 7, 5} {9, 3, 6}

Start with I1 = {8, 7, 5}

Remember, that we are considering 8 because it is lavel 1 of the tree. Next level, we will consider 7 and the next with 5.

The first item = 8

h(8) = 8 mod 3 = 2

I2 = {9, 3, 6}

The first item = 9

h(9) = 9 mod 3 = 0

Level 1

Now, the secons item of set I1 = 7

h(7) = 7 mod 3 = 1

Now, the secons item of set I2 = 3

h(7) = 3 mod 3 = 0

### Like this:

Like Loading...