Home | About | Sematext search-lucene.com search-hadoop.com
 Search Hadoop and all its subprojects:

Switch to Plain View
HDFS >> mail # user >> how to design the mapper and reducer for the below problem


+
parnab kumar 2013-06-14, 04:41
+
Azuryy Yu 2013-06-14, 08:37
+
Harsh J 2013-06-14, 09:39
+
John Lilley 2013-06-16, 19:02
+
John Lilley 2013-06-16, 19:03
+
parnab kumar 2013-06-14, 14:06
+
Sanjay Subramanian 2013-06-14, 16:15
Copy link to this message
-
RE: How to design the mapper and reducer for the following problem
You basically have a "record similarity scoring and linking" problem -- common in data-quality software like ours.  This could be thought of as computing the cross-product of all records, counting the number of hash keys in common, and then outputting those that exceed a threshold.  This is very slow for large data because of N-squared size of intermediate data set or at least the number of iterations.

If you have assurance that the frequency of a given HASH value is low, such that all instances of records containing a given hash key can fit into memory, it can be done as follows:

1)      Mapper1 outputs four tuples with hash as key: {HASH1, DOCID}, {HASH2,DOCID},{HASH3,DOCID},{HASH4,DOCID} per input record

2)      Reducer1 loads all tuples with same HASH into memory.

3)      Reducer1 outputs all tuples { DOCID1, DOCID2, HASH } that share the hash key (nested loop, but only output where DOCID1 < DOCID2)

4)      Mapper2 load tuples from Reducer1 and treats { DOCID1, DOCID2 } as key

5)      Reducer2 counts {DOCID1,DOCID2} instances and outputs DOCID pairs for those exceeding threshold.

If you have no such assurance, make Mapper1 a map-only job, and replace Reducer1 with a new job that joins by HASH.  Joins are not standardized in MR but can be done with MultipleInputs, and of course Pig has this built in.  Searching on "Hadoop join" will give you some ideas of how to implement in straight MR.

John
From: parnab kumar [mailto:[EMAIL PROTECTED]]
Sent: Friday, June 14, 2013 8:06 AM
To: [EMAIL PROTECTED]
Subject: How to design the mapper and reducer for the following problem

An input file where each line corresponds to a document .Each document is identfied by some fingerPrints .For example a line in the input file
is of the following form :

input:
---------------------
DOCID1   HASH1 HASH2 HASH3 HASH4
DOCID2   HASH5 HASH3 HASH1 HASH4

The output of the mapreduce job should write the pair of DOCIDS which share a threshold number of HASH in common.

output:
--------------------------
DOCID1 DOCID2
DOCID3 DOCID5
+
John Lilley 2013-06-16, 19:40