hadoop-common-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Tarandeep Singh <tarand...@gmail.com>
Subject Re: multiple file input
Date Fri, 19 Jun 2009 23:11:11 GMT
oh my bad, I was not clear-

For FileB, you will be running a second map reduce job. In mapper, you can
use the Bloom Filter, created in first map reduce job (if you wish to use)
to eliminate the lines whose keys dont match. Mapper will emit key,value
pair, where key is teh field on which you want to do comparison and value is
the whole line.

when the key,value pairs go to reducers, then you have lines from FileB
sorted on the field yon want to use for comparison. Now you can read
contents of FileA (note that if you ran first job with N reducers, you will
have N paritions of FileA and you want to read only the partition meant for
this reducer). Content of FileA is also sorted on the field, Now you can
easily compare the lines from two files.

CloudBase- cloudbase.sourceforge.net has code for doing join this fashion.

Let me know if you need more clarification.

-Tarandeep

On Fri, Jun 19, 2009 at 3:45 PM, pmg <parmod.mehta@gmail.com> wrote:

>
> thanks tarandeep
>
> Correct if I am wrong that when I map FileA mapper created key,value pair
> and sends across to the reducer. If so then how can I compare when FileB is
> not even mapped yet.
>
>
> Tarandeep wrote:
> >
> > On Fri, Jun 19, 2009 at 2:41 PM, pmg <parmod.mehta@gmail.com> wrote:
> >
> >>
> >> For the sake of simplification I have simplified my input into two files
> >> 1.
> >> FileA 2. FileB
> >>
> >> As I said earlier I want to compare every record of FileA against every
> >> record in FileB I know this is n2 but this is the process. I wrote a
> >> simple
> >> InputFormat and RecordReader. It seems each file is read serially one
> >> after
> >> another. How can my record read have reference to both files at the same
> >> line so that I can create cross list of FileA and FileB for the mapper.
> >>
> >> Basically the way I see is to get mapper one record from FileA and all
> >> records from FileB so that mapper can compare n2 and forward them to
> >> reducer.
> >
> >
> > It will be hard (and inefficient) to do this in Mapper using some custom
> > intput format. What you can do is use Semi Join technique-
> >
> > Since File A is smaller, run a map reduce job that will output key,value
> > pair where key is the field or set of fields on which you want to do the
> > comparison and value is the whole line.
> >
> > The reducer is simply an Identity reducer which writes the files. So your
> > fileA has been partitioned on the field(s). you can also create bloom
> > filter
> > on this field and store it in Distributed Cache.
> >
> > Now read FileB, load Bloom filter into memory and see if the field from
> > line
> > of FileB is present in Bloom filter, if yes emit Key,Value pair else not.
> >
> > At reducers, you get the contents of FileB partitioned just like contents
> > of
> > fileA were partitioned and at a particular reducer you get lines sorted
> on
> > the field you want to do the comparison, At this point you read the
> > contents
> > of FileA that reached this reducer and since its contents were sorted as
> > well, you can quickly go over the two lists.
> >
> > -Tarandeep
> >
> >>
> >>
> >> thanks
> >>
> >>
> >>
> >> pmg wrote:
> >> >
> >> > Thanks owen. Are there any examples that I can look at?
> >> >
> >> >
> >> >
> >> > owen.omalley wrote:
> >> >>
> >> >> On Jun 18, 2009, at 10:56 AM, pmg wrote:
> >> >>
> >> >>> Each line from FileA gets compared with every line from FileB1,
> >> >>> FileB2 etc.
> >> >>> etc. FileB1, FileB2 etc. are in a different input directory
> >> >>
> >> >> In the general case, I'd define an InputFormat that takes two
> >> >> directories, computes the input splits for each directory and
> >> >> generates a new list of InputSplits that is the cross-product of the
> >> >> two lists. So instead of FileSplit, it would use a FileSplitPair that
> >> >> gives the FileSplit for dir1 and the FileSplit for dir2 and the
> record
> >> >> reader would return a TextPair with left and right records (ie.
> >> >> lines). Clearly, you read the first line of split1 and cross it by
> >> >> each line from split2, then move to the second line of split1 and
> >> >> process each line from split2, etc.
> >> >>
> >> >> You'll need to ensure that you don't overwhelm the system with either
> >> >> too many input splits (ie. maps). Also don't forget that N^2/M grows
> >> >> much faster with the size of the input (N) than the M machines can
> >> >> handle in a fixed amount of time.
> >> >>
> >> >>> Two input directories
> >> >>>
> >> >>> 1. input1 directory with a single file of 600K records - FileA
> >> >>> 2. input2 directory segmented into different files with 2Million
> >> >>> records -
> >> >>> FileB1, FileB2 etc.
> >> >>
> >> >> In this particular case, it would be right to load all of FileA into
> >> >> memory and process the chunks of FileB/part-*. Then it would be much
> >> >> faster than needing to re-read the file over and over again, but
> >> >> otherwise it would be the same.
> >> >>
> >> >> -- Owen
> >> >>
> >> >>
> >> >
> >> >
> >>
> >> --
> >> View this message in context:
> >> http://www.nabble.com/multiple-file-input-tp24095358p24119228.html
> >> Sent from the Hadoop core-user mailing list archive at Nabble.com.
> >>
> >>
> >
> >
>
> --
> View this message in context:
> http://www.nabble.com/multiple-file-input-tp24095358p24119864.html
> Sent from the Hadoop core-user mailing list archive at Nabble.com.
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message