data-miningapriorihashtree

Reading a 3-candidate hash tree structure

I am trying to figure out how to properly navigate a hash tree structure given a certain transaction. I already have the answer to the question, but I'm not entirely sure how they arrived at it.

Here is a link to the hash tree structure hash tree structure

Question: Given a transaction that contains items {1,3,4,5,8}, which of the hash tree leaf nodes will be visited when finding the candidates of the transaction?

Answer: L1, L3, L5, L9, and L11

I understand that this is some form of Apriori, so my initial thought process is to look at the first node level {1, 4, 7}, {2, 5, 8}, and {3, 6, 9} and if any of those 3 candidate itemsets contain at least 1 number in the transaction then proceed to the next node level, where you would check if at least 2 numbers were in the transaction, but that doesn't work at all. If anyone could help explain how to navigate this type of hash tree using a transaction it would be extremely helpful.

Solution

  • 1,4,7 is not an itemset.

    Every branch is a list of numbers modulo 3. If x mod 3==1 you take the first branch, if x mod 3==2 the second, and x mod 3==0 the last branch.

    Itemset {145}