       finding the k-nearest neighbour

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

```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
deviations
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
solutions.
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

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

E-mail: ludsteck at zew.de

```

• 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