병렬화 된 레코드 결합 - 복수 키 일치

Question

MapReduce를 사용하여 병렬화 된 레코드 결합 시스템을 구축하고자했습니다. 언어는 중요하지 않습니다. Hadoop과 같은 기존 라이브러리를 사용하거나 필요한 경우 내 라이브러리를 작성할 수 있습니다. 걱정하지 않아도됩니다.

그러나 계속해서 문제가되는 것은 여러 기준에 일치하는 레코드가 필요하다는 것입니다. 예를 들어, 사람의 이름이 또는 인 사람의 전화 번호를 기반으로 한 레코드를 일치시켜야하지만, 반드시 그 사람의 이름이 및 인 전화 번호와 일치 할 필요는 없습니다.

1. '존 스미스'와 '555-555-5555'
2. '제인 스미스'와 '555-555-5555'
: 각 레코드에 대해 다음 키 주어진 예를 들어

,

3. '존 스미스'와 '555-555-1111'

나는 시스템이 세 가지 기록을들이 키 중 하나에 일치하는지 파악하고,이 하나의 결합 된 레코드로 결합 할 두 이름 ('John Smith'및 'Jane Smith')도 두 전화 번호로 ('555-555-5555'및 '555-555-1111 ').

MapReduce를 사용하여이 작업을 수행 할 수 있습니까? 그렇다면 Map 함수가 생성 한 키를 일치 시켜서 일치하는 모든 레코드를 Reduce 함수에 전달할 수 있습니다. * 또는이 작업을 수행 할 수있는 다른 방법이 있습니까? 필자의 유일한 요구 사항은 필자가 병렬화해야한다는 것이다.

[*] 참고 : Reduce 함수가 각 작업에 대해 하나의 결과를 생성하는 Reduce 함수 대신 하나의 결합 된 레코드를 생성하는 방식으로 Reduce 함수를 사용할 수 있다고 가정합니다 .

Answer 1

레코드 그룹을 식별하는 데 도움이되는 각 레코드에 의미있는 키를 실제로 만들 수 없기 때문에 여기서는 맵이 유용하다고 생각하지 않습니다.

Reduce를 사용하여 구현할 수 없습니다. 'Jane Smith'를 쿼리하면 첫 번째 레코드가 쿼리와 관련되어 있으므로 검색 할 수 없으므로 무시됩니다. 실제로 파일에 모든 레코드가 생길 때까지 이름과 숫자를 함께 연결할 수 있습니다. 모든 일치 항목을 선택하는 유일한 방법은 새 링크를 찾는 것을 중지 할 때까지 반복적으로 목록을 검사하는 것입니다.

이것은 병렬 처리가 매우 쉽습니다. 일부 스레드 사이에서 레코드를 공유하고 각 레코드가 새 링크를 검색 할 수 있습니다. 이 세트를 데이터 고리로 취급하여 최신 정보로 검색하는 지점을 기록 할 수 있도록하고 모든 스레드가 완전한 루프를 완료 한 후에는 완료했음을 알 수 있습니다.

Answer 2

map/reduce 패러다임에서 확실히 할 수 있습니다.

'스미스'또는 '555'로 시작하는 전화 번호가 포함 된 항목과 일치한다고 가정 해 보겠습니다. 예를 들어 검색 문자열을 "smith |^555"로 정규화합니다.지도 단계에서, 당신이 할 것 :

• 존 스미스/555-555-5555 → K : 스미스 |^(555), V = (존 스미스, 555-555-5555)
• 신원 미상/555-555-5555 → K : 스미스 |^(555), V = (신원 미상, 555-555-5555)
• 존 스미스/555-555-1111 → K : 스미스 |^(555), V = (John Smith, 555-555-1111)

같은 키 ("smith |^555")를 모두 입력 했으므로 이제는 같은 감속기 인스턴스로 전달됩니다.

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

이제 감속 단계에서 인스턴스를 생성 할 수 있습니다. 이름에 대한 해시 세트 및 숫자에 대한 해시 세트를 작성한 다음, 값 배열을 처리하면 이름 해시 세트의 모든 키와 숫자 해시 세트의 모든 키를 출력합니다.