Steve Lewis
20110622, 22:16
Jason
20110623, 00:13
Lance Norskog
20110623, 00:33
John Armstrong
20110623, 12:45
Steve Lewis
20110623, 17:07
Jason
20110623, 18:06


Algorithm for cross product
Assume I have two data sources A and B
Assume I have an input format and can generate key values for both A and B I want an algorithm which will generate the cross product of all values in A having the key K and all values in B having the key K. Currently I use a mapper to generate key values for A and have the reducer get all values in B with key K and hold them in memory. It works but might not scale. Any bright ideas?  Steven M. Lewis PhD 4221 105th Ave NE Kirkland, WA 98033 2063841340 (cell) Skype lordjoe_com 
Re: Algorithm for cross product
I remember I had a similar problem.
The way I approached it was by partitioning one of the data sets. At high level these are the steps: Suppose you decide to partition set A. Each partition represents a subset/range of the A keys and must be small enough to fit records in memory. Each partition gets sent to a separate reducer by the mapper and partitioner logic. The second data set B then is *duplicated* for each of the reducers again using some trivial logic in mapper and partitioner. This assumes that the reducers can process record from both A and B sets. Also all records from A preceed ones from B which is trivially done by sort comparator. When a reducer receives a record from A set, it stores it in memory. When a record from set B arrives, the cross product is computed with all A records already in memory and results are emitted. The job should scale in space as long as you have enough reducers assigned and will scale in time with more reducer machines. Sent from my iPhone On Jun 22, 2011, at 3:16 PM, Steve Lewis <[EMAIL PROTECTED]> wrote: > Assume I have two data sources A and B > Assume I have an input format and can generate key values for both A and B > I want an algorithm which will generate the cross product of all values in A having the key K and all values in B having the > key K. > Currently I use a mapper to generate key values for A and have the reducer get all values in B with key K and hold them in memory. > It works but might not scale. > > Any bright ideas? > >  > Steven M. Lewis PhD > 4221 105th Ave NE > Kirkland, WA 98033 > 2063841340 (cell) > Skype lordjoe_com > > 
Re: Algorithm for cross product
If you have scaling problems, check out the Mahout project. They are
all about distributed scalable linear algebra & more. http://mahout.apache.org Lance On Wed, Jun 22, 2011 at 5:13 PM, Jason <[EMAIL PROTECTED]> wrote: > I remember I had a similar problem. > The way I approached it was by partitioning one of the data sets. At high level these are the steps: > > Suppose you decide to partition set A. > > Each partition represents a subset/range of the A keys and must be small enough to fit records in memory. > > Each partition gets sent to a separate reducer by the mapper and partitioner logic. > > The second data set B then is *duplicated* for each of the reducers again using some trivial logic in mapper and partitioner. > > This assumes that the reducers can process record from both A and B sets. Also all records from A preceed ones from B which is trivially done by sort comparator. > > When a reducer receives a record from A set, it stores it in memory. > When a record from set B arrives, the cross product is computed with all A records already in memory and results are emitted. > > The job should scale in space as long as you have enough reducers assigned and will scale in time with more reducer machines. > > > Sent from my iPhone > > On Jun 22, 2011, at 3:16 PM, Steve Lewis <[EMAIL PROTECTED]> wrote: > >> Assume I have two data sources A and B >> Assume I have an input format and can generate key values for both A and B >> I want an algorithm which will generate the cross product of all values in A having the key K and all values in B having the >> key K. >> Currently I use a mapper to generate key values for A and have the reducer get all values in B with key K and hold them in memory. >> It works but might not scale. >> >> Any bright ideas? >> >>  >> Steven M. Lewis PhD >> 4221 105th Ave NE >> Kirkland, WA 98033 >> 2063841340 (cell) >> Skype lordjoe_com >> >> >  Lance Norskog [EMAIL PROTECTED] 
Re: Algorithm for cross product
On Wed, 22 Jun 2011 15:16:02 0700, Steve Lewis <[EMAIL PROTECTED]>
wrote: > Assume I have two data sources A and B > Assume I have an input format and can generate key values for both A and B > I want an algorithm which will generate the cross product of all values in > A > having the key K and all values in B having the > key K. > Currently I use a mapper to generate key values for A and have the reducer > get all values in B with key K and hold them in memory. > It works but might not scale. > > Any bright ideas? I was just thinking about a more general version of this problem. If we think of a mapper as saying "for all <foo> in <set A> do <something>", then what if we have two inputs? That is, what if we want to map over the cartesian product of two input sets? "for all <(foo,bar)> in <set A x set B> do <something>" I'm thinking this should be a new InputFormat, which takes two InputFormats (with configuration information) as parameters. Then an InputSplit for the product input is an input entry from A "times" an InputSplit from B. I haven't worked out the details, but this should be the basic idea. Thoughts? 
Re: Algorithm for cross product
The approach you suggest is similar to what I am currently doing but it
requires you to size the partitions to the memory available on the reducer. This is a nontrivial task and is not necessarily guaranteed to scale. It is true that the simplest approach is to break one of the sets into sufficiently small partitions to hold a partition in memory and then generate the Cartesian product but it is a hack and makes assumptions about partition size. One elegant solution would involve an ability to restart one of the input splitters and replay the input data from set A several times until the mapper had generated all sets of the form <key,(ai,bj> On Wed, Jun 22, 2011 at 5:13 PM, Jason <[EMAIL PROTECTED]> wrote: > I remember I had a similar problem. > The way I approached it was by partitioning one of the data sets. At high > level these are the steps: > > Suppose you decide to partition set A. > > Each partition represents a subset/range of the A keys and must be small > enough to fit records in memory. > > Each partition gets sent to a separate reducer by the mapper and > partitioner logic. > > The second data set B then is *duplicated* for each of the reducers again > using some trivial logic in mapper and partitioner. > > This assumes that the reducers can process record from both A and B sets. > Also all records from A preceed ones from B which is trivially done by sort > comparator. > > When a reducer receives a record from A set, it stores it in memory. > When a record from set B arrives, the cross product is computed with all A > records already in memory and results are emitted. > > The job should scale in space as long as you have enough reducers assigned > and will scale in time with more reducer machines. > > > Sent from my iPhone > > On Jun 22, 2011, at 3:16 PM, Steve Lewis <[EMAIL PROTECTED]> wrote: > > > Assume I have two data sources A and B > > Assume I have an input format and can generate key values for both A and > B > > I want an algorithm which will generate the cross product of all values > in A having the key K and all values in B having the > > key K. > > Currently I use a mapper to generate key values for A and have the > reducer get all values in B with key K and hold them in memory. > > It works but might not scale. > > > > Any bright ideas? > > > >  > > Steven M. Lewis PhD > > 4221 105th Ave NE > > Kirkland, WA 98033 > > 2063841340 (cell) > > Skype lordjoe_com > > > > >  Steven M. Lewis PhD 4221 105th Ave NE Kirkland, WA 98033 2063841340 (cell) Skype lordjoe_com 
Re: Algorithm for cross product
> One elegant solution would involve an ability to restart one of the input splitters and replay the input data from set A several times until the mapper had generated all sets of the form <key,(ai,bj>
By replaying A several times, did you actually mean reading A set B times? Cause in this case you may end up with a lot of IO use depending on size of your sets and a size of a single record. With partitioning approach, IO reads are naturally reduced by choosing partition size larger. Sent from my iPhone On Jun 23, 2011, at 10:07 AM, Steve Lewis <[EMAIL PROTECTED]> wrote: > The approach you suggest is similar to what I am currently doing but it requires you to size the partitions to the memory available on the reducer. This is a nontrivial task and is not necessarily guaranteed to scale. It is true that the simplest approach is to break one of the sets into sufficiently small partitions to hold a partition in memory and then generate the Cartesian product but it is > a hack and makes assumptions about partition size. > One elegant solution would involve an ability to restart one of the input splitters and replay the input data from set A several times until the mapper had generated all sets of the form <key,(ai,bj> > > > On Wed, Jun 22, 2011 at 5:13 PM, Jason <[EMAIL PROTECTED]> wrote: > I remember I had a similar problem. > The way I approached it was by partitioning one of the data sets. At high level these are the steps: > > Suppose you decide to partition set A. > > Each partition represents a subset/range of the A keys and must be small enough to fit records in memory. > > Each partition gets sent to a separate reducer by the mapper and partitioner logic. > > The second data set B then is *duplicated* for each of the reducers again using some trivial logic in mapper and partitioner. > > This assumes that the reducers can process record from both A and B sets. Also all records from A preceed ones from B which is trivially done by sort comparator. > > When a reducer receives a record from A set, it stores it in memory. > When a record from set B arrives, the cross product is computed with all A records already in memory and results are emitted. > > The job should scale in space as long as you have enough reducers assigned and will scale in time with more reducer machines. > > > Sent from my iPhone > > On Jun 22, 2011, at 3:16 PM, Steve Lewis <[EMAIL PROTECTED]> wrote: > > > Assume I have two data sources A and B > > Assume I have an input format and can generate key values for both A and B > > I want an algorithm which will generate the cross product of all values in A having the key K and all values in B having the > > key K. > > Currently I use a mapper to generate key values for A and have the reducer get all values in B with key K and hold them in memory. > > It works but might not scale. > > > > Any bright ideas? > > > >  > > Steven M. Lewis PhD > > 4221 105th Ave NE > > Kirkland, WA 98033 > > 2063841340 (cell) > > Skype lordjoe_com > > > > > > > >  > Steven M. Lewis PhD > 4221 105th Ave NE > Kirkland, WA 98033 > 2063841340 (cell) > Skype lordjoe_com > > 
