Mailing-List: contact mahout-dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: mahout-dev@lucene.apache.org
Received-SPF: neutral (nike.apache.org: local policy)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
  s=s1024; d=yahoo.fr;
  h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:MIME-Version:Content-Type:Content-Transfer-Encoding;
  b=dK4u1F29mW5kBJ+/fRhtLmdzVO/1tsq4vlEKuf8SKwzgaf8uRV0Qs183LkapcTO0PzudwE6tPAMI7J6dFEoYT5GvDJgH0n0qQOSi5g8kNLdEf4nL2OAOTEs5mY3ZubDYoHaLu0jwtrzd4W2xkMymMo8w5JDn6E1hkGCjydPDHNc=;
Message-ID: <281390.56457.qm@web26303.mail.ukl.yahoo.com>
Date: Wed, 17 Jun 2009 10:45:30 +0000 (GMT)
From: deneche abdelhakim <a_deneche@yahoo.fr>
Subject: [GSOC] Thoughts about Random forests map-reduce implementation
To: mahout-dev@lucene.apache.org
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable


As we talked about in the following discussion (A), I'm considering two way=
s to implement a distributed map-reduce builder.=0A=0AGiven the reference i=
mplementation, the easiest implementation is the following:=0A=0A* the data=
 is distributed to the slave nodes using the DistributedCache=0A* each mapp=
er loader the data in-memory when in JobConfigurable.configure()=0A* each t=
ree is built by one mapper=0A* the Job doesn't really need any input data, =
it may be possible to implement our own InputFormat that generates InputSpl=
it s using the configuration parameters (number of trees)=0A* the mapper us=
es DecisionTree.toString() to output the tree in a String=0A* the main prog=
ram builds the forest using DecisionTree.parse(String) for each tree=0A=0AP=
ros:=0A* the easiest implementation because the actual ref. code can be use=
d as it is, and the distributed implementation can benefit from future opti=
mizations of the ref. code=0A=0ACons:=0A* because its based on the ref. imp=
lementation, it will be very slow when dealing with large datasets. For exa=
mple, with half of the KDD 99 dataset (a file of about 350 Mb), building on=
e single tree will took more than 12 hours (in fact I stopped the program a=
fter 12 hours) in a core 2 2Ghz with 3 Gb of RAM laptop !!!=0A* if the slav=
e nodes contain many computing cores it would be interesting to launch para=
llel mappers in every slave node to exploit the multi-threading. But as I d=
idn't found a way to share a memory variable between the mappers, each mapp=
er must load its own copy of the Data in memory !=0A=0AImportant:=0A* The r=
ef. implementation memory usage will probably change when the Information G=
ain computing will be optimized, in this case an out-of-core approach could=
 become viable=0A=0ASo I'm asking, what to do next ?=0A* go on with this im=
plementation=0A* optimize the IG computing=0A* consider the "Distributed Im=
plementation B", see (A), which deals with BIG datasets and should not need=
 any IG optimization, but its code has nearly nothing to do with the ref. i=
mplementation=0A=0A(A) http://markmail.org/message/mgap2nuhnl4kokeu=0A=0A=
=0A