Determinare in modo efficiente la relazione sottoinsieme molti a molti

Sto facendo analisi del paniere di mercato. Ho un insieme di transazioni . Ogni transazione è un insieme di articoli che sono stati acquistati. Poi ho un set di set di elementi (cioè un insieme di elementi) di cui voglio determinare il supporto. Il supporto di un set di elementi è definito come il numero di transazioni di cui il set di elementi è un sottoinsieme. Sono interessato solo a quei set di prodotti con un supporto superiore a qualche soglia. Per coloro che sanno, questo è parte dell ' algoritmo Apriori che sto cercando di implementare in C (sì, lo so ci sono implementazioni disponibili).

^{Per chiarire: una transazione è un insieme di elementi che sono stati effettivamente acquistati insieme da un cliente. Un set di elementi è un insieme di elementi che non sono stati effettivamente acquistati insieme ma di cui si desidera calcolare il supporto. Di 'che hai le transazioni {Bread, Butter, Milk}; {Bread, Jam}; {Pane, burro, marmellata}. Quindi il supporto del set di elementi {Bread, Butter} sarebbe 2 (assoluto) o 67%.}

Che cosa sto facendo ora:

1. Ogni transazione viene archiviata come un albero di ricerca binario e bilanciata una volta utilizzando Day -Stout-Warren .
2. Per gli itemset con dimensione 1, il supporto viene calcolato passando attraverso tutte le transazioni e quindi attraverso il BST. Ciò richiede O (n * log (t) * 1) per set di elementi , dove t è la dimensione media di una transazione e il numero di transazioni. Durante il calcolo di questo supporto, viene memorizzato un elenco ordinato degli ID di transazione corrispondenti senza ulteriori sforzi computazionali.
3. Gli insiemi di dimensioni 2 e superiori sono sempre costruiti come unione di due set di articoli più piccoli. In questo caso, prendo semplicemente gli elenchi ordinati degli ID di transazione corrispondenti e calcoliamo la sottosequenza comune più lunga, che in questo caso particolare prende O (n) dove n è la dimensione dell'elenco più grande (poiché le liste sono ordinate, possiamo percorrili contemporaneamente)
4. Gli elementi di dimensioni 2 e superiori vengono considerati solo quando sono l'unione di due set di elementi più piccoli con supporto sufficiente (che è il punto dell'algoritmo di Apriori).

Funziona, ma non è molto efficiente. Sto lavorando in C, utilizzando un'implementazione standard dell'albero di ricerca binario e un'implementazione standard della sua funzione exists . Semplicemente a causa della complessità computazionale molto tempo è utilizzato nel passaggio 2 sopra: 93,53% su una corsa tipica. Mi piacerebbe ridurre questo.

Quale potrebbe essere un modo più efficiente per calcolare il supporto per set di dimensioni 1?

L'implementazione C per riferimento:

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