a) Construct a hash tree for the above candidate 3-itemsets. Assume the tree uses a hash function where all odd-numbered items are hashed to the left child of a node, and all even-numbered items are hashed to the right child of a node. A candidate itemset is inserted into the tree by hashing on each successive item in the candidate and then following the appropriate branch of the tree according to the hash value. Once a leaf node is reached, the candidate is inserted based on one of the following conditions: If the depth of the leaf node is 3 (the root is assumed to be at depth 0), then the candidate is inserted regardless of the number of itemsets already stored at the node. If the depth of the leaf node is less than 3, then the candidate can be inserted as long as the number of itemsets stored at the node is less than maxsize (assume maxsize = 2). If the depth of the leaf node is less than 3 and the number of itemsets stored at the node is equal to maxsize, then the leaf node is converted into an internal node. New leaf nodes are created as children of the old leaf node. Candidate itemsets previously stored in the old leaf node are distributed to the children based on their hash values. The candidate is also hashed to its appropriate leaf node. (b) How many leaf nodes are there in the candidate hash tree? (c) Consider a transaction that contains the following items: {1, 3, 4, 5, 6}. Using the hash tree constructed in part(a), which leaf nodes will be checked against the transaction?
MAC
Datamining Exercise:
Consider the following set of candidate 3-itemsets:
{1, 2, 3}, {1, 2, 5}, {1, 3, 5}, {1, 5, 6}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {2, 4, 6}, {3, 4, 5}, {3, 4, 6}
(a) Construct a hash tree for the above candidate 3-itemsets. Assume the tree uses a hash function where all odd-numbered items are hashed to the left child of a node, and all even-numbered items are hashed to the right child of a node.
A candidate itemset is inserted into the tree by hashing on each successive item in the candidate and then following the appropriate branch of the tree according to the hash value. Once a leaf node is reached, the candidate is inserted based on one of the following conditions:
If the depth of the leaf node is 3 (the root is assumed to be at depth 0), then the candidate is inserted regardless of the number of itemsets already stored at the node.
If the depth of the leaf node is less than 3, then the candidate can be inserted as long as the number of itemsets stored at the node is less than maxsize (assume maxsize = 2).
If the depth of the leaf node is less than 3 and the number of itemsets stored at the node is equal to maxsize, then the leaf node is converted into an internal node. New leaf nodes are created as children of the old leaf node. Candidate itemsets previously stored in the old leaf node are distributed to the children based on their hash values. The candidate is also hashed to its appropriate leaf node.
(b) How many leaf nodes are there in the candidate hash tree?
(c) Consider a transaction that contains the following items: {1, 3, 4, 5, 6}. Using the hash
tree constructed in part(a), which leaf nodes will be checked against the transaction?
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
