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