Return-Path: X-Original-To: apmail-hadoop-common-user-archive@www.apache.org Delivered-To: apmail-hadoop-common-user-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 176E8EAA7 for ; Tue, 8 Jan 2013 03:27:15 +0000 (UTC) Received: (qmail 53508 invoked by uid 500); 8 Jan 2013 03:27:10 -0000 Delivered-To: apmail-hadoop-common-user-archive@hadoop.apache.org Received: (qmail 53298 invoked by uid 500); 8 Jan 2013 03:27:10 -0000 Mailing-List: contact user-help@hadoop.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: user@hadoop.apache.org Delivered-To: mailing list user@hadoop.apache.org Received: (qmail 53287 invoked by uid 99); 8 Jan 2013 03:27:09 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 08 Jan 2013 03:27:09 +0000 X-ASF-Spam-Status: No, hits=2.5 required=5.0 tests=FREEMAIL_REPLY,HTML_MESSAGE,RCVD_IN_DNSWL_LOW,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (nike.apache.org: domain of balijamahesh.mca@gmail.com designates 209.85.217.170 as permitted sender) Received: from [209.85.217.170] (HELO mail-lb0-f170.google.com) (209.85.217.170) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 08 Jan 2013 03:27:03 +0000 Received: by mail-lb0-f170.google.com with SMTP id j14so47887lbo.15 for ; Mon, 07 Jan 2013 19:26:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=umdyJtv2XO9dMKES+/Kd5iJpQGs9IlWGcdJlcW+HFX8=; b=wPQWZcBi60AunudZY/ahA4JI6nGwP6x6uwok4OeIkD/YNDkcAD2WOcuNvpCJNX/H8s yHQWFhpzASQ8uIOvOMD5r8c3WTeP5NYQtdacEm6QSiEmHwSVOYtw2vSYlknFfE9PBBfV OIz+GDJ4QrVrSId97bADuFd3p/3ckrJ7t3kWNFoCWtxIoyjiJTL2IA76glkvPbzoggsS /I+bd+o0xnBm8DivdImORGYAyN3uUi99fXkn7dytdtjHt1+8Qz27928LsKbMhLIYwL94 v/ZuswtWunkJWb7iNozHVHQZnjvhaESHiTtk38TC6si6Ca2gCnlfPgQo79fG+JuOQDPT rqdg== MIME-Version: 1.0 Received: by 10.152.124.68 with SMTP id mg4mr59155749lab.51.1357615602610; Mon, 07 Jan 2013 19:26:42 -0800 (PST) Received: by 10.112.74.198 with HTTP; Mon, 7 Jan 2013 19:26:42 -0800 (PST) In-Reply-To: References: <869970D71E26D7498BDAC4E1CA92226B3FCD8FA2@MBX021-E3-NJ-2.exch021.domain.local> <869970D71E26D7498BDAC4E1CA92226B3FCD901F@MBX021-E3-NJ-2.exch021.domain.local> Date: Tue, 8 Jan 2013 08:56:42 +0530 Message-ID: Subject: Re: Binary Search in map reduce From: Mahesh Balija To: user@hadoop.apache.org Content-Type: multipart/alternative; boundary=f46d043bd8febc322804d2be8314 X-Virus-Checked: Checked by ClamAV on apache.org --f46d043bd8febc322804d2be8314 Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Hi Jamal, Another simple approach if your data is too huge and cannot fit into memory would be just to use the MultipleInputs mechanism. Where your MR job will have two mappers one emitting the records from "the graph" file and other from changes file. Any how your reducer will aggregate the records based on the same key (the graph key and changes key). In order you to know which record is been emitted from which file you can use key as the graph key for both the mappers but MapWritable as your value in mapper where the key in the mapwritable will be some constant say 1 -> the graph and 2 -> changes and value will be the actual value. Now the only thing left for you is to append your changes to the actual key and emit the final result. Best, Mahesh Balija, Calsoft Labs. On Tue, Jan 8, 2013 at 5:47 AM, jamal sasha wrote: > awesome. > thanks > > > On Mon, Jan 7, 2013 at 4:11 PM, John Lilley wro= te: > >> Let=92s call these =93the graph=94 and =93the changes=94.**** >> >> ** ** >> >> Will both the graph and the changes fit into memory?**** >> >> Yes -> You do not have a Hadoop-scale problem. Just write some code >> using HashTable or Dictionary.**** >> >> ** ** >> >> Will the graph fit into memory once it is partitioned amongst all of the >> nodes?**** >> >> Yes -> You can get away without a join. Partition the graph and the >> changes like below, but instead of doing a join on each partition, strea= m >> the changes against the graph partition in memory, using a HashTable for >> the graph partition.**** >> >> ** ** >> >> Otherwise, you can do this in a few steps. Realize that you are doing a >> parallel join. A parallel join can be done in hadoop by a simple modulo= of >> the keys of the graph and the changes. So first, create a couple of MR >> jobs just to partition =93the graph=94 and =93the changes=94 into N buck= ets using >> (key%N). I **think** this is pretty straightforward because if your >> mapper adds new_key=3D(key%N) to the tuple and you use N reducers you ge= t >> this behavior automatically (is it really that simple? someone with more= MR >> expertise please correct me=85). Once the graph and the changes are >> partitioned, run another MR job to (1) join each graph partition file to >> the corresponding changes partition file (2) process the changes into th= e >> graph (3) write out the resulting graph. This part is not a parallel jo= in; >> it is a bunch of independent simple joins. Finally, merge the resulting >> graphs together. **** >> >> ** ** >> >> You may find that it isn=92t even this easy. If nothing fits into memor= y >> and you must perform a non-trivial graph traversal for each change recor= d, >> you have something must harder to do.**** >> >> ** ** >> >> FYI top google results for joins in Hadoop here: >> https://www.google.com/search?q=3Djoins+in+hadoop&aq=3Df&oq=3Djoins+in+h= adoop&aqs=3Dchrome.0.57j60l2j0l2j62.670&sugexp=3Dchrome,mod=3D14&sourceid= =3Dchrome&ie=3DUTF-8 >> **** >> >> ** ** >> >> john**** >> >> ** ** >> >> *From:* jamal sasha [mailto:jamalshasha@gmail.com] >> *Sent:* Monday, January 07, 2013 4:43 PM >> *To:* user@hadoop.apache.org >> *Subject:* Re: Binary Search in map reduce**** >> >> ** ** >> >> Hi**** >> >> Thanks for the reply. So here is the intent.**** >> >> I process some data and output of that processing is this set of json >> documents outputting {key:[values]} (This is essentially a form of grap= h >> where each entry is an edge)**** >> >> Now.. I process a different set of data and the idea is to modify the >> existing document based on this new data.**** >> >> If the key is present then add/modify values.**** >> >> Else... create new key:[values] json object and save.**** >> >> ** ** >> >> So, the first step is checking whether the key is present or not..**** >> >> So thats why I thought of doing the binary search.**** >> >> Any suggestions?**** >> >> ** ** >> >> ** ** >> > > --f46d043bd8febc322804d2be8314 Content-Type: text/html; charset=windows-1252 Content-Transfer-Encoding: quoted-printable Hi Jamal,

=A0=A0=A0=A0=A0=A0 Another simple approach if your data is= too huge and cannot fit into memory would be just to use the MultipleInput= s mechanism.
=A0=A0=A0=A0=A0=A0 Where your MR job will have two mappers = one emitting the records from "the graph" file and other from cha= nges file.
=A0=A0=A0=A0=A0=A0
=A0=A0=A0=A0=A0=A0 Any how your reducer will aggrega= te the records based on the same key (the graph key and changes key).
= =A0=A0=A0=A0=A0=A0 In order you to know which record is been emitted from w= hich file you can use key as the graph key for both the mappers but MapWrit= able as your value in mapper where the key in the mapwritable will be some = constant say 1 -> the graph and 2 -> changes and value will be the ac= tual value.

=A0=A0=A0=A0=A0=A0 Now the only thing left for you is to append your ch= anges to the actual key and emit the final result.

Best,
Mahesh B= alija,
Calsoft Labs.

On Tue, Jan 8, 20= 13 at 5:47 AM, jamal sasha <jamalshasha@gmail.com> wrote= :
awesome.
thanks

=
On Mon, Jan 7, 2013 at 4:11 PM, John Lilley <john.lilley@redpoint= .net> wrote:

Let=92s call these =93the= graph=94 and =93the changes=94.

=A0<= /p>

Will both the graph and t= he changes fit into memory?

Yes -> You do not have= a Hadoop-scale problem.=A0 Just write some code using HashTable or Diction= ary.

=A0<= /p>

Will the graph fit into m= emory once it is partitioned amongst all of the nodes?=

Yes -> You can get awa= y without a join.=A0 Partition the graph and the changes like below, but in= stead of doing a join on each partition, stream the changes against the graph partition in memory, using a HashTable for the graph partition.<= u>

=A0<= /p>

Otherwise, you can do thi= s in a few steps.=A0 Realize that you are doing a parallel join.=A0 A paral= lel join can be done in hadoop by a simple modulo of the keys of the graph and the changes.=A0 So first, create a couple of MR jobs just= to partition =93the graph=94 and =93the changes=94 into N buckets using (k= ey%N).=A0 I *think* this is pretty straightforward because if your m= apper adds new_key=3D(key%N) to the tuple and you use N reducers you get this behavior automatically (is it really that = simple? someone with more MR expertise please correct me=85).=A0=A0 Once th= e graph and the changes are partitioned, run another MR job to (1) join eac= h graph partition file to the corresponding changes partition file (2) process the changes into the graph (3) write ou= t the resulting graph.=A0 This part is not a parallel join; it is a bunch o= f independent simple joins.=A0 Finally, merge the resulting graphs together= .=A0

=A0<= /p>

You may find that it isn= =92t even this easy.=A0 If nothing fits into memory and you must perform a = non-trivial graph traversal for each change record, you have something must harder to do.

=A0<= /p>

FYI top google results fo= r joins in Hadoop here: https://www.google.com/search?q=3Djoins+in+hadoop&aq=3Df&oq=3Djoins= +in+hadoop&aqs=3Dchrome.0.57j60l2j0l2j62.670&sugexp=3Dchrome,mod=3D= 14&sourceid=3Dchrome&ie=3DUTF-8

=A0<= /p>

john=

=A0<= /p>

From: jamal sa= sha [mailto:jama= lshasha@gmail.com]
Sent: Monday, January 07, 2013 4:43 PM
To: user= @hadoop.apache.org
Subject: Re: Binary Search in map reduce

=A0

Hi

=A0Thanks for the reply. So here is the intent.

I process some data and output of that processing is= this set of json documents outputting {key:[values]} =A0(This is essential= ly a form of graph where each entry is an edge)

Now.. I process a different set of data and the idea= is to modify the existing document based on this new data.

If the key is present then add/modify values.=

Else... create new key:[values] json object and save= .

=A0

So, the first step is checking whether the key is pr= esent or not..

So thats why I thought of doing the binary search.

Any suggestions?

=A0

=A0



--f46d043bd8febc322804d2be8314--