Reading a 3-candidate hash tree structure

Question

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

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.

Answer 1

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}

• 1 mod 3 = 1, thus the first branch in the top level
• 4 mod 3 = 1, thus the first branch in the second level
• 5 mod 3 = 2, thus the second branch in the third level (if it exists).