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 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).

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