# Efficiently determining many-to-many subset relation

I'm doing market basket analysis. I have a set of transactions. Every transaction is a set of items that were bought. I then have a set of itemsets (i.e. a set of items) that I want to determine the support for. The support of an itemset is defined as the number of transactions of which the itemset is a subset. I'm only interested in those itemsets with a support above some threshold. For those who know, this is part of the Apriori algorithm which I'm trying to implement in C (yes, I know there are implementations available).

To clarify: a transaction is a set of items that were actually bought together by a customer. An itemset is a set of items that wasn't actually bought together but that you want to compute the support of. Say you have the transactions {Bread, Butter, Milk}; {Bread, Jam}; {Bread, Butter, Jam}. Then the support of the itemset {Bread, Butter} would be 2 (absolute) or 67%.

What I'm doing now:

1. Every transaction is stored as a binary search tree, and balanced once using Day-Stout-Warren.
2. For the itemsets with size 1, support is calculated by going through all transactions and then through the BST. This takes O(n*log(t)*1) per itemset, where t is the average size of a transaction and n the number of transactions. While computing this support, a sorted list of the matching transaction IDs is stored without additional computational effort.
3. The itemsets of size 2 and higher are always constructed as the union of two smaller itemsets. In this case, I simply take the sorted lists of matching transaction IDs, and compute the longest common subsequence, which in this particular case takes O(n) where n is the size of the largest list (because the lists are sorted, we can walk through them simultaneously).
4. Itemsets of size 2 and higher are only considered when they are the union of two smaller itemsets with sufficient support (which is the point of the Apriori algorithm).

This works, but isn't very efficient. I'm working in C, using a standard implementation of the binary search tree and a standard implementation of its `exists` function. Simply due to the computational complexity a lot of time is used in step 2 above: 93.53% on a typical run. I'd like to reduce this.

What could be a more efficient way to compute the support for itemsets of size 1?

The C implementation for reference:

``````typedef struct bs_node {
ap_item data;
struct bs_node* left;
struct bs_node* right;
} bs_node;
typedef bs_node bs_tree;

bool bs_exists(bs_tree* tree, ap_item target) {
if (tree == NULL)
return false;
else if (tree->data < target)
return bs_exists(tree->right, target);
else if (tree->data > target)
return bs_exists(tree->left, target);
else
return true;
}
``````
• "I then have a set of itemsets" Is an itemset just a set of items? How is that different from the set of items you are calling a Transaction? "The number of transactions of which the itemset is a subset" What? Can you re-word that somehow? It makes no sense to me whatsoever. Commented Dec 7, 2015 at 15:28
• @GlenPeterson thank you for your time. I guess this wasn't very clear indeed for someone not familiar with the Apriori algorithm already. I updated the edit with an example and some more clarification. I hope it is clear now, if there are more questions just ask!
– user76821
Commented Dec 7, 2015 at 15:36
• Why would you not use SVD to find eigen-baskets (aka itemsets) then truncate for eigen-baskets with an eigen-value below a given threshold? It is O(k m^2 n + k' n^3) for matrix m*n and constants k=4 and k'=22 so it isn't screaming fast, but it is a "do it once and then use the results". You could use compressed sensing and if you have some prior categories you could have striated sampling to make it go much faster. Commented Dec 7, 2015 at 18:15
• @EngrStudent that sounds like a nice idea, but my goal is to implement the Apriori algorithm. It is just an exercise; the algorithm is outperformed on basically any dataset by newer algorithms.
– user76821
Commented Dec 7, 2015 at 23:15

First, I'd recommend a better data structure for your transactions. Whereas a binary tree is preferable to a sequential list (assuming the list is more than about 10 items), it's still log(n) to find an item. Your code would execute a whole lot faster if your store receipt stored the items in a hash table rather than in a binary tree. Rather than `O(n log(t))`, finding all of the transactions that contain an item is `O(n)`.

A Google search for "hashtable in C" gives multiple implementations that should work well.

Second, assuming that you're going to run the algorithm for multiple itemsets, it makes sense to pre-compute things so that you don't have to search the transactions at all. Instead, when the program starts go through all of the transactions and build a huge hash table of all items and the transactions in which they occur. So at startup you would have:

``````Butter: 1, 7, 9, 23, 86, 87, 92, ...
Bread: 2, 9, 33, 87, ...
Toothpaste: 8, 6, 12, 15, 43, ...
``````

The numbers are transaction Ids.

This is just an inverted index of the transactions. Rather than saying what items are in each transaction, it says what transaction contains the item.

Then, when somebody asks you to look for {Bread, Butter}, you quickly union those two sets.

If the inverted index is too large to fit into memory, you can easily create it in a database. Or, if you don't have a database, you use map-reduce techniques. The result is that you have the inverted index on disk and an index (surprise, another hash table) in memory. The index contains the item (i.e. Bread, Jam, etc.) and its location in the file.

Finally, a note on profiling:

Considering that the program doesn't do much at all in the single-item case but search for items in transactions, it's no surprise at all that it spends the vast majority of its time in the binary search. Even if you rewrite your code to use the hash table, it's still going to spend the vast majority of its time in the lookup code. Unless, of course, you pre-compute the single-item case as I suggested. Then all that lookup time is amortized over all of the searches.