CODEWITHSUNDEEP
algorithmsearchindexingcomputational-geometryknn
stemm
stemm

Reputation: 6050

Find nearset neighbours in large set

I have large set of points in multidimensional space. And I'd like to find few neighbours (within the neighborhood) for any given point (require is to avoid scanning of all points).

I want to know if my solution is appropriate:

Pre processing:

  1. Define set of ortogonal axises
  2. Make a projection of each point on each axis
  3. Each projection is associated with its distance from the start point of axis (key) and identifier of point (value). Index projections - put all of them into sorted set (e.g. tree set)
dist = distance of projection to the start point of axis
point_num = number of point 
sorted_set.put( dist, point_num )

To find neighbours for any given point:

  1. Find its projection on each axis
  2. Using idexes - find nearest projections on each exis
  3. To find actual neighbours - intersect of all results
dx = radius of neighborhood (some constant) 

dist_1 = distance of projection of given point to start point of axis_1 
list_1 = sorted_set_1.get_sub_set( dist_1 - dx, dist_1 + dx )

dist_2 = distance of projection of given point to start point of axis_2
list_2 = sorted_set_2.get_sub_set( dist_2 - dx, dist_2 + dx ) 

return intersection_of( list_1, list_2 )

Here is a simple example:

enter image description here

Intersecting [2, 4, 1] and [4, 5] produces answer [4]

Please, point me, if I have done any mistakes in my algorithm

Thanks

Upvotes: 1

Views: 167

Answers (1)

Nick Larsen
Nick Larsen

Reputation: 18877

You haven't given us instructions on how to build your actual neighbors set, in this case [2, 4, 1] and [4, 5]. Why did you choose 3 elements from one index and 2 from another?

You also state that you'd like to find a few neighbors. How many is a few or should it be an input to your function? In the example you only find one, should the algorithm decide how many you want?

What happens in the case where all of the points are on a line on one of your axis? Then one set is certain to contain all elements.

Upvotes: 1

Related Questions