Similarity join using Hadoop

Question

Sono nuovo di hadoop. Mi piacerebbe avere qualche approccio con te che mi è venuto in mente.

Problema:
2 set di dati: A e B.
Entrambi i set di dati rappresentano canzoni: attribuisce un certo livello superiore, i titoli (1 .. ), interpreti (1 ..).
Ho bisogno di abbinare questi set di dati usando gli algoritmi di uguaglianza o fuzzy (come levenshtein, jaccard, jaro-winkler, ecc.) Basati su titoli ed esecutori.
Le dimensioni del set di dati sono: A = 20-30M, B ~ = 1-6M.

Così qui ci sono approcci che mi si avvicinò con:

1. carico dataset B (il più piccolo) in HDFS. Utilizzare mapreduce rispetto al set di dati A (il più grande), dove:
   fase mappa: per ogni record in A accesso HDFS e tirare i record B per la corrispondenza;
   ridurre fase: scrive coppie id

2. carico di dati A nella cache distirubted (cioè jboss cache) in forma ottimizzata per velocizzare la ricerca. Utilizzare MapReduce contro dataset B, dove:
   mappa fase: per ogni record nella query B cache distribuita per la corrispondenza
   ridurre: scrive coppie id

3. uso MapReduce di unire entrambe le serie di dati, in cui
   fase mappa: ottiene un registra dal set A e set B, fa corrispondere
   riduci fase: lo stesso
   (Sono confuso su quello 1. Primo: join sarà il prodotto cartesiano con trilioni di record, 2 °: non è sicuro di come hadoop può farlo in parallelo cluster)

4. utilizzare alveare (sto guardando proprio ora cercando di capire come plug-in funzioni personalizzate che faranno string matching)

sto loooking per un puntatori, quale approccio sarebbe il miglior candidato o forse ci sono alcuni altri approcci che non vedo.

Answer 1

si potrebbe trovare questo documento e codice utile:

Efficient Parallel Set-Similarity Joins Using MapReduce

ho personalmente implementato in Cascading con buoni risultati. Sfortunatamente il codice è troppo specifico del dominio per il rilascio.

Il punto del lavoro di cui sopra è di ridurre il numero di join alle coppie candidate che sono molto simili, quindi le coppie candidate possono essere confrontate direttamente (in un join MR) utilizzando qualsiasi cocktail di algoritmi rilevanti. Un buon effetto collaterale è che questo join può essere eseguito in modo uniforme all'interno del cluster senza confronti duplicati.

In definitiva si tratta di un'ottimizzazione sull'esecuzione di un cross join tra due set indipendenti o all'interno dello stesso set (il secondo caso implementato in modo leggermente diverso rispetto al primo).

divulgazione: io sono l'autore di Cascading

Answer 2

Si potrebbe desiderare di guardare a questi due documenti di Jimmy Lin:

• Brute Force and Indexed Approaches to Pairwise Document Similarity
• Pairwise Document Similarity in Large Collections with MapReduce

L'approccio si prende dipenderà da che tipo di somiglianza metrica si utilizza, ma un approccio basato su Lucene potrebbe funzionare qui. Potresti anche voler pensare a come suddividere i dati in modo da ridurre il numero di confronti da effettuare.

Answer 3

dare un'occhiata a

1. http://dbs.uni-leipzig.de/en/publication/learning_based_er_with_mr -> Valutazione della prodzuct cartesiana di due (grandi) di ingresso imposta

   Tuttavia si dovrebbe davvero cercare di evitare di fare calcoli sulla similarità in coppia (Levenshtein, ecc.) sul prodotto cartesiano. Anche con cluster di grandi dimensioni occorreranno ore o giorni anche per i set di dati di medie dimensioni.

2. http://dbs.uni-leipzig.de/en/publication/lb_for_mr_based_er -> Spiega come Blocco/Clustering avvicina con confronti a coppie di ogni cluster può essere realizzata in modo uniforme, garantendo nel contempo compiti caricati (single e dual-source)