Combinaison d'enregistrements parallélisés - appariement sur plusieurs clés

Question

J'ai envisagé d'utiliser MapReduce pour créer un système de combinaison d'enregistrements parallélisés. La langue n'a pas d'importance, je peux utiliser une bibliothèque préexistante telle que Hadoop ou construire la mienne si nécessaire, cela ne m'inquiète pas. Le problème que je continue à rencontrer, cependant, est que j'ai besoin que les enregistrements soient appariés selon plusieurs crit'eres. Par exemple: Il se peut que je doive faire correspondre les enregistrements en fonction du nom de la personne ou le numéro de téléphone de la personne, mais pas nécessairement le nom de la personne et.

Par exemple, étant donné les clés suivantes pour chaque enregistrement:

1. 'John Smith' et '555-555-5555'
2. 'Jane Smith' et '555-555-5555'
3. « John Smith » et « 555-555-1111 »

Je veux que le système de prendre les trois dossiers, comprendre qu'ils correspondent à l'une des clés, et de les combiner en un seul enregistrement combiné qui a deux noms («John Smith» et «Jane Smith») comme les deux numéros de téléphone («555-555-5555» et «555-555-1111»).

Est-ce quelque chose que je peux accomplir en utilisant MapReduce? Si c'est le cas, comment procéder pour faire correspondre les clés produites par la fonction Carte afin que tous les enregistrements correspondants puissent être transmis à la fonction Réduire. * Sinon, y a-t-il un moyen différent/meilleur de le faire? Ma seule exigence réelle est que j'en ai besoin parallélisé.

[*] Remarque: Je suppose que la fonction Réduire peut être utilisée de telle sorte que chaque appel à la fonction Réduire produise un enregistrement combiné unique plutôt que la fonction Réduire produisant un résultat unique pour l'ensemble du travail .

Answer 1

Je ne pense pas que Map soit utile ici, parce que vous ne pouvez pas vraiment créer une clé significative pour chaque enregistrement qui aidera à identifier les groupes d'enregistrements.

Il n'est pas possible de l'implémenter en utilisant Réduire non plus. Considérez l'exemple que vous avez vous-même donné ... Si vous faites une requête pour 'Jane Smith', vous ne pouvez pas détecter à ce moment-là que le premier enregistrement est lié à la requête et l'ignorera donc. En fait, vous pourriez finir par enchaîner les noms et les numéros jusqu'à ce que vous ayez tous les enregistrements dans le fichier. La seule façon de récupérer toutes les correspondances est de parcourir itérativement la liste jusqu'à ce que vous arrêtiez de trouver de nouveaux liens.

Ceci est très facile à paralléliser, vous pouvez simplement partager les enregistrements entre un certain nombre de threads, et chacun peut rechercher ses propres enregistrements pour de nouveaux liens. Je suggère de traiter ces ensembles comme des anneaux de données, de sorte que vous puissiez enregistrer le point que vous recherchez avec les informations les plus à jour, et vous savez que vous avez terminé une fois que tous les threads ont fait une boucle complète.

Answer 2

Vous pouvez certainement le faire dans le paradigme map/reduce. Supposons que vous correspondiez à quelque chose qui contient «smith» ou aux numéros de téléphone commençant par «555». Vous pouvez canoniser votre chaîne de recherche dans "smith |^555", par exemple.Dans la phase de la carte, vous feriez:

• John Smith/555-555-5555 → K: smith |^555, V = (John Smith, 555-555-5555)
• Jane Doe/555-555-5555 → K: smith |^555, V = (Jane Doe, 555-555-5555)
• John Smith/555-555-1111 → K: smith |^555, V = (John Smith, 555-555-1111)

Puisque vous leur avez donné la même clé ("smith |^555"), ils seront tous transférés à la même instance de réducteur, qui sera maintenant, en entrée:

K: smith |^555, V: [(John Smith, 555-555-5555), (Jane Smith, 555-555-5555), (John Smith, 555-555-1111))

Maintenant, dans votre étape réducteur, vous pouvez instancier un hashset pour les noms et un autre pour les nombres, et lorsque vous avez terminé le traitement du tableau de valeurs, affichez toutes les clés du hashset des noms et toutes les clés du hashset number.