Efficiently determining many-to-many subset relation

Question

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;
}

Answer 1

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.