CODEWITHSUNDEEP
algorithmsearchdata-structurescomputational-geometrynearest-neighbor
Inspiration
Inspiration

Reputation: 83

3D Nearest neighbour for query points located far away from set of points

I need to answer a lot of queries about finding nearest neighbour in pointset, locating far away from the query point. All approaches I've found so far work bad in this case (for example, k-d tree may have O(N) per query) or require use of Voronoi diagram (I have ~10m points so Voronoi diagram is too expensive).
Is there any known algorithm designed for such a task?

Upvotes: 2

Views: 850

Answers (2)

TilmannZ
TilmannZ

Reputation: 1889

Some multidimensional indexes have kNN queries that could be easily adapted to you needs, especially with k==1. kNN algorithms usually have to first estimate the approximate nearest neighbour distance, then they use this distance to perform a range query. In R-Trees or quadtrees, this estimation can be done efficiently by finding the node that is closest to your search point. Then they take one point from the closest node, calculate the distance to the search point, and then perform a range query based on this distance, usually with some multiplier because k>1. This should be reasonable efficient even if the search point is far away.

If you are searching for one point only (k=1) then you could adapt this algorithm to use a range query that is exactly based on the closest point you found, no extra extension to get k>1 points.

If you are using Java, you could use my open-source implementations here. There is also a PH-Tree (a kind of quadtree, but much more space efficient and faster to load), which uses the same kNN approach.

Upvotes: 0

gsamaras
gsamaras

Reputation: 73366

The problem here are the distances. You see, when a query is far from your dataset, then the kd-tree has to check many points, thus slowing down the query time.

The scenario you are facing is hard for the Nearest Neighbor Structures in general (and it's not the usual case), but if I were you, I would give a shot with Balanced Box-Decomposition trees, where you can read more about their algorithm and data structure.

Upvotes: 1

Related Questions