Re: finding the k-nearest neighbour
- To: mathgroup at smc.vnet.net
- Subject: [mg26154] Re: finding the k-nearest neighbour
- From: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>
- Date: Thu, 30 Nov 2000 01:04:00 -0500 (EST)
- Organization: Universitaet Leipzig
- References: <8vvr6e$3hj@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hi, you don't like : http://www.mathsource.com/Content/Applications/ComputerScience/0208-471 Regards Jens Ludsteck wrote: > > 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