Software Programming

Kunuk Nykjaer

K-nearest neighbor in 2D dimension space

with 3 comments


K-nearest neighbor

There are miscellaneous algorithms for searching nearest neighbors.

An alternative method is to use grid indexing strategy.
Slowly expand the grid boxes from the center to find the k-nearest neighbors.
The grid is used as a filtering mechanism to reduce the search space.

This works fast for distributed data across the space and is a good alternative algorithm for dynamic data that changes position frequently.

Reference links:

Project implemented in C# is available at Github:
A survey of techniques for fixed radius near neighbor searching:

knn

The origin is in ring 0.
The origin can anywhere in the box and the distance to test on first iteration must be at least 1 x grid distance. The first iteration starts with data from ring 0 and 1.

The algorithm goes like this:

i = 0
Point origin
list currRing = empty
list nextRing = empty
list temp
while all rings not explored
   i = i + 1
   temp = empty
   for all point in nextRing test distance between origin and point
       if distance is within i * grid put it in currRing
       else put it in temp

   nextRing = empty
   Add all from temp to nextRing

   temp = empty
   if(i==1) temp = points from ring 0 and ring 1
   else temp = points from ring i

   For all point in temp test distance between origin and point
       if distance is within i * grid put it in currRing
       else put it in nextRing

   If there are at least k points in currRing then exit while loop
end while loop

if currRing count is < k then add all from nextRing to currRing

sort currRing by distance
take first k from currRing


knn example

Grid version algorithm:
Apply algorithm described above.
Searching: O(n * m) where m is grid cells and k << n.

Naive version algorithm:
For origin point check the distance to every other point.
Take k first items sorted by distance.
Searching: O(n log n)

About these ads

Written by kunuk Nykjaer

January 21, 2013 at 9:36 pm

3 Responses

Subscribe to comments with RSS.

  1. Good day! Would you mind if I share your blog with my zynga group?
    There’s a lot of folks that I think would really appreciate your content. Please let me know. Thank you

    Adrienne

    February 21, 2013 at 12:09 am

  2. hello
    can you give me your mail address or contact information, i have a problem to ask from you.
    Ahmad.

    ahmad

    October 7, 2014 at 9:57 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 42 other followers

%d bloggers like this: