You are viewing a plain text version of this content. The canonical link for it is here.
Posted to common-user@hadoop.apache.org by elton sky <el...@gmail.com> on 2011/04/29 14:02:37 UTC
Applications creates bigger output than input?
One of assumptions map reduce made, I think, is that size of map's output is
smaller than input. Although we can see many applications have the same size
of output with input, like, sort, merge,etc.
For my benchmark purpose, I am looking for some non-trivial, real life
applications which creates *bigger* output than its input. Trivial example I
can think about is cross join...
I really appreciate if you share your knowledge with me.
Re: Applications creates bigger output than input?
Posted by John Meagher <jo...@gmail.com>.
Another case is augmenting data. This is sometimes done outside of MR
in an ETL flow, but can be done as an MR job. Doing something like
this is using Hadoop to handle the scaling issues, but really isn't
what MR is intended for.
A real example of this is:
* Input: standard apache weblog
* Data added...
- Geolocation of IP
- Decoding URL
- Adding information based on visited URL / Ref URL ...
- Adding information based on the user
* Output complex binary object to a sequence file
On Fri, Apr 29, 2011 at 08:02, elton sky <el...@gmail.com> wrote:
> One of assumptions map reduce made, I think, is that size of map's output is
> smaller than input. Although we can see many applications have the same size
> of output with input, like, sort, merge,etc.
> For my benchmark purpose, I am looking for some non-trivial, real life
> applications which creates *bigger* output than its input. Trivial example I
> can think about is cross join...
>
> I really appreciate if you share your knowledge with me.
>
Re: Applications creates bigger output than input?
Posted by Ted Dunning <td...@maprtech.com>.
Cooccurrence analysis is commonly used in recommendations. These produce
large intermediates.
Come on over to the Mahout project if you would like to talk to a bunch of
people who work on these problems.
On Fri, Apr 29, 2011 at 9:31 PM, elton sky <el...@gmail.com> wrote:
> Thank you for suggestions:
>
> Weblog analysis, market basket analysis and generating search index.
>
> I guess for these applications we need more reduces than maps, for handling
> large intermediate output, isn't it. Besides, the input split for map
> should
> be smaller than usual, because the workload for spill and merge on map's
> local disk is heavy.
>
> -Elton
>
> On Sat, Apr 30, 2011 at 11:22 AM, Owen O'Malley <om...@apache.org>
> wrote:
>
> > On Fri, Apr 29, 2011 at 5:02 AM, elton sky <el...@gmail.com>
> wrote:
> >
> > > For my benchmark purpose, I am looking for some non-trivial, real life
> > > applications which creates *bigger* output than its input. Trivial
> > example
> > > I
> > > can think about is cross join...
> > >
> >
> > As you say, almost all cross join jobs have that property. The other case
> > that almost always fits into that category is generating an index. For
> > example, if your input is a corpus of documents and you want to generate
> > the
> > list of documents that contain each word, the output (and especially the
> > shuffle data) is much larger than the input.
> >
> > -- Owen
> >
>
Re: Applications creates bigger output than input?
Posted by elton sky <el...@gmail.com>.
Thanks Robert, Niels
Ye, I think text manipulation, especially ngram is a good application for
me.
Cheers
On Fri, May 20, 2011 at 12:57 AM, Robert Evans <ev...@yahoo-inc.com> wrote:
> I'm not sure if this has been mentioned or not but in Machine Learning with
> text based documents, the first stage is often a glorified word count
> action. Except much of the time they will do N-Gram. So
>
> Map Input:
> "Hello this is a test"
>
> Map Output:
> "Hello"
> "This"
> "is"
> "a"
> "test"
> "Hello" "this"
> "this" "is"
> "is" "a"
> "a" "test"
> ...
>
>
> You may also be extracting all kinds of other features form the text, but
> the tokenization/n-gram is not that CPU intensive.
>
> --Bobby Evans
>
> On 5/19/11 3:06 AM, "elton sky" <el...@gmail.com> wrote:
>
> Hello,
> I pick up this topic again, because what I am looking for is something not
> CPU bound. Augmenting data for ETL and generating index are good examples.
> Neither of them requires too much cpu time on map side. The main bottle
> neck
> for them is shuffle and merge.
>
> Market basket analysis is cpu intensive in map phase, for sampling all
> possible combinations of items.
>
> I am still looking for more applications, which creates bigger output and
> not CPU bound.
> Any further idea? I appreciate.
>
>
> On Tue, May 3, 2011 at 3:10 AM, Steve Loughran <st...@apache.org> wrote:
>
> > On 30/04/2011 05:31, elton sky wrote:
> >
> >> Thank you for suggestions:
> >>
> >> Weblog analysis, market basket analysis and generating search index.
> >>
> >> I guess for these applications we need more reduces than maps, for
> >> handling
> >> large intermediate output, isn't it. Besides, the input split for map
> >> should
> >> be smaller than usual, because the workload for spill and merge on
> map's
> >> local disk is heavy.
> >>
> >
> > any form of rendering can generate very large images
> >
> > see: http://www.hpl.hp.com/techreports/2009/HPL-2009-345.pdf
> >
> >
> >
>
>
Re: Applications creates bigger output than input?
Posted by Niels Basjes <Ni...@basjes.nl>.
Something I've seen in the past is code that has the input
"something"
and outputs
"s"
"so"
"som"
"some"
"somet"
"someth"
"somethi"
"somethin"
"something"
So the output number of records is the same as the length of the input text.
Niels
2011/5/19 elton sky <el...@gmail.com>:
> Hello,
> I pick up this topic again, because what I am looking for is something not
> CPU bound. Augmenting data for ETL and generating index are good examples.
> Neither of them requires too much cpu time on map side. The main bottle neck
> for them is shuffle and merge.
>
> Market basket analysis is cpu intensive in map phase, for sampling all
> possible combinations of items.
>
> I am still looking for more applications, which creates bigger output and
> not CPU bound.
> Any further idea? I appreciate.
>
>
> On Tue, May 3, 2011 at 3:10 AM, Steve Loughran <st...@apache.org> wrote:
>
>> On 30/04/2011 05:31, elton sky wrote:
>>
>>> Thank you for suggestions:
>>>
>>> Weblog analysis, market basket analysis and generating search index.
>>>
>>> I guess for these applications we need more reduces than maps, for
>>> handling
>>> large intermediate output, isn't it. Besides, the input split for map
>>> should
>>> be smaller than usual, because the workload for spill and merge on map's
>>> local disk is heavy.
>>>
>>
>> any form of rendering can generate very large images
>>
>> see: http://www.hpl.hp.com/techreports/2009/HPL-2009-345.pdf
>>
>>
>>
>
--
Met vriendelijke groeten,
Niels Basjes
Re: Applications creates bigger output than input?
Posted by Robert Evans <ev...@yahoo-inc.com>.
I'm not sure if this has been mentioned or not but in Machine Learning with text based documents, the first stage is often a glorified word count action. Except much of the time they will do N-Gram. So
Map Input:
"Hello this is a test"
Map Output:
"Hello"
"This"
"is"
"a"
"test"
"Hello" "this"
"this" "is"
"is" "a"
"a" "test"
...
You may also be extracting all kinds of other features form the text, but the tokenization/n-gram is not that CPU intensive.
--Bobby Evans
On 5/19/11 3:06 AM, "elton sky" <el...@gmail.com> wrote:
Hello,
I pick up this topic again, because what I am looking for is something not
CPU bound. Augmenting data for ETL and generating index are good examples.
Neither of them requires too much cpu time on map side. The main bottle neck
for them is shuffle and merge.
Market basket analysis is cpu intensive in map phase, for sampling all
possible combinations of items.
I am still looking for more applications, which creates bigger output and
not CPU bound.
Any further idea? I appreciate.
On Tue, May 3, 2011 at 3:10 AM, Steve Loughran <st...@apache.org> wrote:
> On 30/04/2011 05:31, elton sky wrote:
>
>> Thank you for suggestions:
>>
>> Weblog analysis, market basket analysis and generating search index.
>>
>> I guess for these applications we need more reduces than maps, for
>> handling
>> large intermediate output, isn't it. Besides, the input split for map
>> should
>> be smaller than usual, because the workload for spill and merge on map's
>> local disk is heavy.
>>
>
> any form of rendering can generate very large images
>
> see: http://www.hpl.hp.com/techreports/2009/HPL-2009-345.pdf
>
>
>
Re: Applications creates bigger output than input?
Posted by elton sky <el...@gmail.com>.
Hello,
I pick up this topic again, because what I am looking for is something not
CPU bound. Augmenting data for ETL and generating index are good examples.
Neither of them requires too much cpu time on map side. The main bottle neck
for them is shuffle and merge.
Market basket analysis is cpu intensive in map phase, for sampling all
possible combinations of items.
I am still looking for more applications, which creates bigger output and
not CPU bound.
Any further idea? I appreciate.
On Tue, May 3, 2011 at 3:10 AM, Steve Loughran <st...@apache.org> wrote:
> On 30/04/2011 05:31, elton sky wrote:
>
>> Thank you for suggestions:
>>
>> Weblog analysis, market basket analysis and generating search index.
>>
>> I guess for these applications we need more reduces than maps, for
>> handling
>> large intermediate output, isn't it. Besides, the input split for map
>> should
>> be smaller than usual, because the workload for spill and merge on map's
>> local disk is heavy.
>>
>
> any form of rendering can generate very large images
>
> see: http://www.hpl.hp.com/techreports/2009/HPL-2009-345.pdf
>
>
>
Re: Applications creates bigger output than input?
Posted by Steve Loughran <st...@apache.org>.
On 30/04/2011 05:31, elton sky wrote:
> Thank you for suggestions:
>
> Weblog analysis, market basket analysis and generating search index.
>
> I guess for these applications we need more reduces than maps, for handling
> large intermediate output, isn't it. Besides, the input split for map should
> be smaller than usual, because the workload for spill and merge on map's
> local disk is heavy.
any form of rendering can generate very large images
see: http://www.hpl.hp.com/techreports/2009/HPL-2009-345.pdf
Re: Applications creates bigger output than input?
Posted by elton sky <el...@gmail.com>.
Thank you for suggestions:
Weblog analysis, market basket analysis and generating search index.
I guess for these applications we need more reduces than maps, for handling
large intermediate output, isn't it. Besides, the input split for map should
be smaller than usual, because the workload for spill and merge on map's
local disk is heavy.
-Elton
On Sat, Apr 30, 2011 at 11:22 AM, Owen O'Malley <om...@apache.org> wrote:
> On Fri, Apr 29, 2011 at 5:02 AM, elton sky <el...@gmail.com> wrote:
>
> > For my benchmark purpose, I am looking for some non-trivial, real life
> > applications which creates *bigger* output than its input. Trivial
> example
> > I
> > can think about is cross join...
> >
>
> As you say, almost all cross join jobs have that property. The other case
> that almost always fits into that category is generating an index. For
> example, if your input is a corpus of documents and you want to generate
> the
> list of documents that contain each word, the output (and especially the
> shuffle data) is much larger than the input.
>
> -- Owen
>
Re: Applications creates bigger output than input?
Posted by Owen O'Malley <om...@apache.org>.
On Fri, Apr 29, 2011 at 5:02 AM, elton sky <el...@gmail.com> wrote:
> For my benchmark purpose, I am looking for some non-trivial, real life
> applications which creates *bigger* output than its input. Trivial example
> I
> can think about is cross join...
>
As you say, almost all cross join jobs have that property. The other case
that almost always fits into that category is generating an index. For
example, if your input is a corpus of documents and you want to generate the
list of documents that contain each word, the output (and especially the
shuffle data) is much larger than the input.
-- Owen
Re: Applications creates bigger output than input?
Posted by John Meagher <jo...@gmail.com>.
Another case is augmenting data. This is sometimes done outside of MR
in an ETL flow, but can be done as an MR job. Doing something like
this is using Hadoop to handle the scaling issues, but really isn't
what MR is intended for.
A real example of this is:
* Input: standard apache weblog
* Data added...
- Geolocation of IP
- Decoding URL
- Adding information based on visited URL / Ref URL ...
- Adding information based on the user
* Output complex binary object to a sequence file
On Fri, Apr 29, 2011 at 08:02, elton sky <el...@gmail.com> wrote:
> One of assumptions map reduce made, I think, is that size of map's output is
> smaller than input. Although we can see many applications have the same size
> of output with input, like, sort, merge,etc.
> For my benchmark purpose, I am looking for some non-trivial, real life
> applications which creates *bigger* output than its input. Trivial example I
> can think about is cross join...
>
> I really appreciate if you share your knowledge with me.
>