1
$\begingroup$

I'm implementing an algorithm from a paper, and part of it calls for using a "hash tree". Since I'd never heard of that data structure I looked it up on Wikipedia. It turns out that the name hash tree is ambiguous and can be used to refer to three different types of data structures. They are:

  • Hashed Array Tree
  • Hash tree (persistent data structure), an implementation strategy for sets and maps
  • Merkle Tree

After reading about each type of data structure, I'm pretty sure that the paper is using a Merkle tree, but I want to get a second opinion. The only thing that makes me doubt that it might be a Merkle Tree is that it seems like I can find lots of examples of it being used in Cryptography and I only see it mentioned a few times in the data mining papers that I'm reading.

The paper in question is Fast Algorithms for Mining Association Rules and the specific section that I'm referring to can be found on page 4 in section 2.1.2.

I've quoted a section of the relevant text below.

Candidate itemsets Ck are stored in a hashtree. A node of the hash-tree either contains a list of itemsets (a leaf node) or a hash table an (interior node). In an interior node each bucket of the hash table points to another node. The root of the hash-tree is defined to be at depth 1. An interior node at depth d points to nodes at depth d+1. Itemsets are stored in the leaves. When we add an itemset c we start from the root and go down the tree until we reach a leaf. At an interior node at depth d we decide which branch to follow by applying a hash function to the dth item of the itemset. All nodes are initially created as leaf nodes. When the number of itemsets in a leaf node exceeds a specified threshold the leaf node is converted to an interior node.

It should also be noted that this particular data structure is mentioned in other data mining papers that are based off of the apriori algorithm such as in this paper on cyclic association rules. Since it is a data structure that is used often, I'd like to read more about is than simply two paragraphs in a few papers.

Improve this question
$\endgroup$
2
  • $\begingroup$ That description does not sound like a merkle-tree to me. $\endgroup$
    – CodesInChaos
    Jun 8, 2016 at 19:12
  • $\begingroup$ I asked a related question here (crypto.stackexchange.com/questions/42162/…). Read the comments (from @CodesInChaos). There, he explains well why one would use a Merkle tree over say some other type of hash tree. $\endgroup$
    – Thomas Jay Rush
    Dec 8, 2016 at 19:37

1 Answer 1

Reset to default
0
$\begingroup$

It turns out that the Hash Tree mentioned in the paper is pretty much the same as a Merkle Hash Tree. For further clarification see pages 344 & 345: https://www-users.cs.umn.edu/~kumar/dmbook/ch6.pdf.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.