Help me, nearest neighbor problem.

[phaothu365]

Hi everyone,

I am new to computational geometry. As part of my master thesis, I have to solve a popular nearest neighbor problem. My task is to search for a point in a set of some 2000 4-dimensional points which is closest to a given point in the sense of Euclidean distance.

After reading some literatures and rich resources on Internet about this very well known NN problem, I found some helpful methods and variants to deal with it (linear search, space partitioning,e.t.c). However, my application is real time and thus requires fast computation such that the closest point is found as quickly as possible,i.e. search time is the most critical objective.

Can anyone who has experience in this fields suggest me some methods (in the vast quantity of methods available today) as optimal choices for my particular problem?

Thank you very much,

Regards,

Viet

 

[chiro]

Hey phathu365 and welcome to the forums.

Are you allowed to precompute structural information before you do the search?

As an example, let's say you have all of the data already. As an optimization step you could create a spatial organization structure. One such structure that comes to mind is any kind of bounded classification structure.

The simplest examples of such structures include axis aligned bounding boxes or spheres about a point.

The critical part of doing this is creating the optimal classification structure. Your structure could ultimately be some kind of convex-hull which is created based on the density of the number of points in a particular area.

One suggestion would be to create some kind of binary partitioning scheme which combines your spatial classification structures so that each test essentially halves the number of points to search which would effectively reduce your algorithmic time to O(log_2(n)).

What constraints do you have? Can you precompute metadata for the points in question (like binary trees/spatial information/etc) or do you have a hybrid of new/old data where some data is static and the other is dynamic?

 

[phaothu365]

Hey phathu365 and welcome to the forums.

Are you allowed to precompute structural information before you do the search?

As an example, let's say you have all of the data already. As an optimization step you could create a spatial organization structure. One such structure that comes to mind is any kind of bounded classification structure.

The simplest examples of such structures include axis aligned bounding boxes or spheres about a point.

The critical part of doing this is creating the optimal classification structure. Your structure could ultimately be some kind of convex-hull which is created based on the density of the number of points in a particular area.

One suggestion would be to create some kind of binary partitioning scheme which combines your spatial classification structures so that each test essentially halves the number of points to search which would effectively reduce your algorithmic time to O(log_2(n)).

What constraints do you have? Can you precompute metadata for the points in question (like binary trees/spatial information/etc) or do you have a hybrid of new/old data where some data is static and the other is dynamic?

Hi Chiro,

Actually, in my problem, the set of points is static. It means that I have fixed known set of points in 4D. For example {0.125; 0.342; 0.9871; 0.7653} is a typical point in the set of some such 2000 points. Only the query point is dynamic. It means for each time instance I have to SWITFLY identify the closest point to this dynamic points in the set of static points. Quick computation time is the only constraint I have in this problem.

"Are you allowed to precompute structural information before you do the search?"
--> Since all the data points are known and used as offline data set, I can precompute structural information or any kind of manipulation on these data points. As you said, the art of solving this problem boils down to how to create an optimal spatial organization structure. However, there are many partition algorithms available such as k-d tree, R-tree,etc and I am not experienced enough to determine what scheme is optimally suitable for my particular problem. According to your suggestion, should I apply partition scheme used in k-d tree algorithm to my problem? Or what could you suggest as better solutions?