MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: nearest neighbor


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

to download follow:
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?