it will work. But i want to avoid case of computing the median by sub machines. So as to improve upon the complexity, i want the sub machines to just take a random number k and split their data into two sets < and > and then pass the information to host machine which after having all the outputs of sub machines tells them to discard < or > data on basis of something. I want this "something".
On Jul 17, 8:51 pm, Ashish Goel <ashg...@gmail.com> wrote: > WOULDN'T MEDIAN OF MEDIANS WORK? mappers and reducers using hadoop > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > > On Sun, Jul 17, 2011 at 8:57 PM, Dumanshu <duman...@gmail.com> wrote: > > Given billions of integers in a file. Memory Constraints exist so need > > to parallelize. One solution can be to split the file over a 100 > > machines and each machine calculates median of their part using > > quickselect and sends the result to host machine. Now the host > > calculates median of these medians and asks the sub machines to > > discard all the numbers less than this final median. So, map reduce! > > > Now i want to do something like this - > > > Each sub machine has billion/100 integers. It chooses an integer k > > randomly and divides its integers into two parts, one is less than k > > and other set is more than k (like quickselect algo). This machine > > returns to the host basically 3 things, one is k, second and third is > > number of elements in both sets. > > After having all that data from submachines, the host does some > > calculation and asks each machine to discard either the less than set > > or more than set. then whole thing is repeated with lesser number of > > elements. > > > Any ideas about how the host machine would do that and on what basis? > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
