0

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.

Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194
Bill Hamilton
  • 3
  • 1
  • 2

1 Answers1

2

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).
Has QUIT--Anony-Mousse
  • 76,138
  • 12
  • 138
  • 194
  • Ohhh okay, so I need to look at every possible 3-candidate combination in {1, 3, 4, 5, 8} and see which nodes are visited? So {1, 3, 4}, {1, 4, 5}, etc. – Bill Hamilton Apr 13 '16 at 08:58