Apriori Meets Hash Trees:

Making Candidate Checking Fast

One of the most expensive steps in the Apriori algorithm is checking whether candidate itemsets actually appear in a transaction database. Imagine having thousands of candidate itemsets and millions of transactions — you don’t want to check every candidate against every transaction one by one.

This is where the hash tree comes in. Let’s walk through a worked example to see how it speeds things up.

The Setup: Candidate Itemsets

Suppose we have 15 candidate itemsets of length 3:

{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,6},  
{1,4,5}, {1,5,9}, {2,3,4}, {2,3,5}, {2,4,6},  
{3,4,5}, {3,6,7}, {4,5,7}, {4,5,8}, {5,6,7}

Our task: efficiently check which of these appear in a given transaction.

Step 1: The Hash Function

We define a simple hash function:

`h(x)=x mod 3h(x) = x \bmod 3`

h(x)=x mod 3

This maps items into three buckets:

• {1, 4, 7}
• {2, 5, 8}
• {3, 6, 9}

Step 2: The Hash Tree Structure

The rule for building the tree is:

• At the i-th level of the tree, hash on the i-th item of the candidate set.
• At level 1, hash on the first item.
• At level 2, hash on the second item.
• At level 3, hash on the third item (leaf: store candidates).

This way, candidates are distributed across the tree.

Step 3: Partitioning Candidates

Let’s see how our 15 candidates fall into the tree.

Branch 1: Hash on {1, 4, 7}

Candidates starting with 1, 4, or 7 go here: {1,2,4}, {1,4,5}, {4,5,7}

Branch 2: Hash on {2, 5, 8}

Candidates starting with 2, 5, or 8 go here: {2,3,4}, {4,5,8}, {5,6,7}

Branch 3: Hash on {3, 6, 9}

Candidates starting with 3, 6, or 9 go here: {1,3,6}, {1,5,9}, {3,4,5}, {3,6,7}

Get Uzair Ahmad’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Each branch continues in the same way — at deeper levels, we hash on the next item in the candidate set.

Step 4: Subset Checking with a Transaction

Now let’s see this in action with a transaction:

t = {1,3,6,8}

We generate all 3-item subsets of t:

• {1,3,6}
• {1,3,8}
• {1,6,8}
• {3,6,8}

Now, instead of linearly comparing these against all 15 candidates, we use the hash tree:

1. {1,3,6} → first item is 1 → go to branch {1,4,7} → next hash on 3 → eventually find {1,3,6} stored at a leaf. ✅ Match found!
2. {1,3,8} → first item is 1 → branch {1,4,7} → next hash on 3 → no match.
3. {1,6,8} → first item is 1 → branch {1,4,7} → next hash on 6 → no match.
4. {3,6,8} → first item is 3 → branch {3,6,9} → next hash on 6 → search continues, but no exact match.

So, only {1,3,6} is a frequent candidate in this transaction.

Why This Matters

Instead of scanning all 15 candidates for every subset, the hash tree guides us directly to where a candidate might exist. If it’s not there, we skip large chunks of candidates.

In large-scale data mining, this makes Apriori far more efficient.

Takeaways

• Apriori generates a huge number of candidate itemsets.
• Hash trees help by organizing candidates into buckets based on a hash function.
• Checking a transaction becomes a matter of tree traversal, not brute-force comparison.
• In our example, we reduced 15 checks to just a handful of hash lookups.