Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - Two sets of high dimensional points: Find the nearest neighbour in the other set

I have 2 sets: A and B. Both sets contain the same number of high dimensional points. How do I find the nearest neighbour in Set A for every point in Set B?

I thought about using a Voronoi diagram but it seems (according to wikipedia) that it is not suitable for dimensions higher than 2.

Can someone suggest a method to me, please?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

FLANN

If your data do really lie in a high dimensional space, then you could use FLANN.

It actually builds a number of rotated kd-trees and queries (a bit) every single tree, keeping the best results found. It also rotates the data-set to avoid nasty cases.

In the publications section you can read more on how it works.

In Getting FLANN section you can also read the manual.

However, since you wish to perform Nearest Neighbour Searching(NNS) in a high dimensional space, you need to accept the trade-off between time and accuracy (more time comes with more accuracy). That's why FLANN performs approximate NNS (check this answer for more).


LSH

As an alternative, I would suggest the LSH algorithm. Here is E2LSH, which actually implements LSH algorithm. The manual can be found here.

The idea behind the algorithm is that we want the points that lie near to each other to be placed (with a high probability) in the same bucket. However, LSH is devoted in solving the R nearest neighbour problem.

By R-near neighbour data structure, the author probably means that given a query point q, we can answer this question: "Which points of the dataset lie inside radius R from q?".

However, the manual explains how can LSH be used to perform NN searching.


Note that this type of questions are not for this site. I answered to you because you are a new user. Next time make sure you don't forget that. :)


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...