Estensioni Iceberg di PCY

Traduzione e Integrazione delle Lezioni a cura di Sandro Gallo

Home Park Chen Yu Algortmi Randomizzati

Le estensioni iceberg all'algoritmo DHP sono due:

1. Mutliple Hash Table.
   Cioè al passo 1 invece di usare una sola hash, usiamo due o più hash e memorizziamo una bitmap per ogni tabella. Lo spazio occupato non cambia, perchè il numero di bucket resta sempre quello. Per essere un candidato di C2, una coppia deve essere formata da articoli in L1 e avere un bucket frequente per ogni tabella hash.
2. Multistage.
   Invece di cercare i candidati al passo 2, eseguiamo un altro hash ma solo sullle coppie che hanno superato il test di PCY. Il terzo passo, quindi, vede la costruzione di una seconda bitmap associata a quest'ultima tabella hash. Una coppia diventa candidata se:
   1. i, j sono in L1,
   2. l'hash bucket della coppia costruito al passo 1 è frequente,
   3. lo stesso vale per i bucket costruiti al passo 2.

Il multiple hash table aiuta quando molti bucket al passo 1 hanno i counts al di sotto della soglia s. Quindi possiamo raddoppiare i contatori dei bucket e avere molti buckets al di sotto della soglia. Multistage aiuta quando il numero di bucket frequenti al primo passo è alto (50%) ma non tutti. Quindi un secondo hashing riduce il numero dei bucket frequenti significativamente.

Home Park Chen Yu Algortmi Randomizzati