Mailing-List: contact user-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@hadoop.apache.org
Received-SPF: neutral (nike.apache.org: local policy)
MIME-Version: 1.0
In-Reply-To: 
 <CABtCYFwfD7ZsV88Wq19WLGOfHYEZsFFSx6dZBT__YJGwabjVYQ@mail.gmail.com>
References: 
 <CABtCYFzx4k36x0-V8M8T_ovSc6sd4EL-Hhn56jNHRbG5UGbQSA@mail.gmail.com>
 <CAND0qzvR7B-5NXNTLwN7mztNotjqM89ZJBKpZ471jStfP9W8Fg@mail.gmail.com>
 <CABtCYFwfD7ZsV88Wq19WLGOfHYEZsFFSx6dZBT__YJGwabjVYQ@mail.gmail.com>
From: Ted Dunning <tdunning@maprtech.com>
Date: Tue, 28 Aug 2012 11:32:48 -0400
Message-ID: 
 <CAND0qzsZieXK3Prvun3Ee+nfsD0PZpfgXvd8fzOXz1WZMR=E-A@mail.gmail.com>
Subject: Re: best way to join?
To: user@hadoop.apache.org
Content-Type: multipart/alternative; boundary=14dae934059dc8cb9904c85528fd

--14dae934059dc8cb9904c85528fd
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Aug 28, 2012 at 9:48 AM, dexter morgan <dextermorgan4u@gmail.com>wrote:

>
> I understand your solution ( i think) , didn't think of that, in that
> particular way.
> I think that lets say i have 1M data-points, and running knn , that the
> k=1M and n=10 (each point is a cluster that requires up to 10 points)
> is an overkill.
>

I am not sure I understand you.  n = number of points.  k = number of
clusters.  For searching 1 million points, I would recommend thousands of
clusters.


> How can i achieve the same result WITHOUT using mahout, just running on
> the dataset , i even think it'll be in the same complexity (o(n^2))
>

Running with a good knn package will give you roughly O(n log n)
complexity.

--14dae934059dc8cb9904c85528fd
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<br><br><div class=3D"gmail_quote">On Tue, Aug 28, 2012 at 9:48 AM, dexter =
morgan <span dir=3D"ltr">&lt;<a href=3D"mailto:dextermorgan4u@gmail.com" ta=
rget=3D"_blank">dextermorgan4u@gmail.com</a>&gt;</span> wrote:<br><blockquo=
te class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc so=
lid;padding-left:1ex">

<div dir=3D"ltr"><div><br></div><div>I understand your solution ( i think) =
, didn&#39;t think of that, in that particular way.</div><div>I think that =
lets say i have 1M data-points, and running knn , that the k=3D1M and n=3D1=
0 (each point is a cluster that requires up to 10 points)=A0</div>


<div>is an overkill.</div></div></blockquote><div><br></div><div>I am not s=
ure I understand you. =A0n =3D number of points. =A0k =3D number of cluster=
s. =A0For searching 1 million points, I would recommend thousands of cluste=
rs.</div>

<div>=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;=
border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>How can =
i achieve the same result WITHOUT using mahout, just running on the dataset=
 , i even think it&#39;ll be in the same complexity (o(n^2))</div>

</div></blockquote><div><br></div><div>Running with a good knn package will=
 give you roughly O(n log n) complexity.=A0</div><div><br></div></div>

--14dae934059dc8cb9904c85528fd--