MathGroup Archive 2000

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

Search the Archive

finding the k-nearest neighbour

  • To: mathgroup at
  • Subject: [mg26139] finding the k-nearest neighbour
  • From: "Ludsteck" <Ludsteck at>
  • Date: Tue, 28 Nov 2000 01:56:38 -0500 (EST)
  • Sender: owner-wri-mathgroup at

Dear MathGroup members,
I have to find the distance between a number x and its k - nearest 
neighbour in a list of numbers (where k is an integer and distance is 
simply Abs).
This is quite easy in Mathematica. I use

knearest[x_, li_List, k_Integer]:= Sort[ Abs/@(li - x) ][[k]]

However, it is also very inefficient, since the whole list of absolute 
has to be sorted. Now my lists are very long and I have to apply the 
knearest[...] function
several thousands of times. Therefore I have to search for much faster 
I think the fasted way would be to use a priority queue of length k.

Has someone other solutions or can someone provide ready-to-use code for 
priority queues in Mathematica?

Thank you very much,

Johannes Ludsteck
Forschungsbereich Arbeitsmaerkte,
Personalmanagement und Soziale Sicherung
Zentrum fuer europaeische Wirtschaftsforschung
Mannheim (ZEW)
Postfach 103443
D 68934 Mannheim

E-mail: ludsteck at

  • Prev by Date: Re: Simplifying with positive constants
  • Next by Date: Re: Simplifying things
  • Previous by thread: Tridiagonal problem
  • Next by thread: Re: finding the k-nearest neighbour