Data Mining: Hash tree based support counting

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