Park Chen Yu

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Miglioramenti Apriori Estensioni Iceberg

L'algoritmo DHP di Park-Chen-Yu usa le tabelle hash per determinare al primo passo, mentre L1 è stato determinato, tutte quelle coppie che non possono essere frequenti.
Sfrutta il fatto che la memoria principale è molto più grande del numero di insiemi. E assume che i dati sono memorizzati in un flat file, con i record composti da un ID e da una lista di articoli.
L'algoritmo DHP (direct hashing and pruning) per il calcolo di insiemi frequenti di due elementi è composto da due passi:

  1. Passo 1:
    1. Conta tutte le occorrenze di articoli.
    2. Per ogni bucket composto dagli articoli {i1, i2, ..., ik}, calcola la funzione hash di tutte le coppie e incrementa il contatore di ogni bucket nella tabella.
    3. Alla fine del passo, determina L1, gli articoli che occorrono almeno s volte.
    4. Alla fine del passo determina anche quei bucket con contatore >= s. Il punto chiave è che la coppia (i,j) non può essere frequente a meno che il suo bucket non sia frequente, e queste comporranno C2. Sostituisci la hash table con una bitmap, mettendo 1 se la coppia corrisponde a un bucket frequente, zero altrimenti.
  1. La memoria principale contiene quindi tutti gli articoli frequenti, cioè L1.
  2. Contiene anche una bitmap che riassume i risultati del passo 1.
  3. Infine, la memoria principale contiene uan tabella con tutte le coppie di candidati e i loro contatori. Una coppia (i,j) può essere una candidata cioè stare in C2 se le seguenti tre condizioni sono soddisfatte:
    1. (i) i sta in L1,
    2. (ii) j sta in L1,
    3. (iii) hash(i,j) è un bucket frequente.
  4. Durante il passo 2 consideriamo ogni basket e ogni coppia dei suoi articoli, facendo il test sopra. Se una coppia soddisfa le tre condizioni, allora incrementa il suo contatore in memoria, o se non esiste un bucket per questa coppia creane uno nuovo.

DHP funziona meglio di Apriori quando le coppie di articoli da L1 sono troppe per fare entrare in memoria una tabella di coppie di candidati insieme ai relativi contatori. Ancora, il numero di bucket frequenti in DHP è sufficientemente piccolo che la dimensione di C2 è inferiore a quella della memoria. Quando molti bucket non sono frequenti in PCY? Quando ci sono poche coppie frequenti, ma molte coppie sono così infrequenti che la somma dei loro contatori non supera la soglia.

Home Miglioramenti Apriori Estensioni Iceberg