Re: nearest neighbor

• To: mathgroup at smc.vnet.net
• Subject: [mg66184] Re: nearest neighbor
• From: Oliver Ruebenkoenig <ruebenko at uni-freiburg.de>
• Date: Wed, 3 May 2006 02:45:13 -0400 (EDT)
• References: <e2v79h\$nm2\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Hi,

if you would like to find several nearest neighbors then you might want to
try a kd-Tree method. You will find the documenation here:

http://www.imtek.uni-freiburg.de/simulation/mathematica/IMSweb/imsTOC/Data%20Structures/TreesDocu.html

http://www.imtek.uni-freiburg.de/simulation/mathematica/IMSweb/

there is also a mailing list:
http://elmo.imtek.uni-freiburg.de/mailman/listinfo/ims

hth,

oliver

On Sat, 29 Apr 2006, Simons, F.H. wrote:

> Chris,
>
> It is an interesing question how to find the nearest neighbor without
> computing ALL distances. But I would not be surprised if such a solution
> turns out to be slower than computing all distances, e.g. in the
> following way. Finding the nearest neighbor from a set of 10^6 points
> takes less than 0.4 second on my slow computer here at the university.
>
> p = {2, 1, 3};
> mat = Array[Random[Real, {0, 4}] & , {10^6, 3}];
> Extract[mat, Ordering[
>     Total[(Transpose[mat] - p)^2], 1]] // Timing
>
> {0.361 Second, {1.97792, 0.982634, 2.98964}}
>
> Regards,
>
> Fred Simons
> Eindhoven University of Technology
>
> > -----Original Message-----
> > From: Kulp, Chris [mailto:Chris.Kulp at EKU.EDU]
To: mathgroup at smc.vnet.net
> > Subject: [mg66184]  nearest neighbor
> >
> >
> > Hello:
> >
> > I am in interested in finding the nearest neighbor for points
> > in a space whose dimension is greater than two.  How can I do
> > this in Mathematica without computing the distances between
> > all of the points? In particular, I am interested in
> > developing a Mathematica notebook for the false nearest
> > neighbor algorithm used in nonlinear time series analysis.
> >
> >
> >
> >
> > Thank you for any help you can give to me.
> >
> >
> >
> > Chris Kulp
> >
> >
> >
> > Dr. Christopher W. Kulp, Ph.D.
> >
> > Assistant Professor of Physics
> >
> > Eastern Kentucky University
> >
> > Moore 351
> >
> > 521 Lancaster Ave.
> >
> > Richmond, KY 40475
> >
> > 859.622.1528
> >
> > chris.kulp at eku.edu
> >
> > http://people.eku.edu/kulpc
> >
> >
> >
> >
>
>

Oliver Ruebenkoenig, <ruebenko at uni-freiburg.de>
Phone: ++49 +761 203 7388

```

• Prev by Date: Re: "In progress" saving of data collected using Reap/Sow
• Next by Date: Re: Evaluating integrals
• Previous by thread: Re: Is it possible for me to implement associative arrays this way?
• Next by thread: Root's third argument?