0
$\begingroup$

I know I already asked a similar question over here: Finding the closest point in a set to another point in n-dimensional space: efficiently

But now my question is different. I have many points (potentially millions) in a high-dimensional space. Given a point P, I need to find other points close by. Obviously, searching the entire universe is completely inefficient, so I need to find a way to break it up into smaller parts—"communities" of points. As you can see in my other post above, my initial approach was to have static (unchanging) points at each of the extremes of the axis (i.e.: (100,0,0,0), (0,100,0,0), (0,0,100,0), (0,0,0,100)), and then define what group a point belongs to base on which static point it is near. (All points in the universe are between 0-100 on each axis.)

However, this approach is flawed: if, for example, two points are near the origin, they may be near each other, but belong to different groups (closer to different static points).

Is there a better approach? I thought about breaking the universe up into many hypercubes, however, determining what hypercube a point should belong to seems inefficient.

Thanks for your help!

$\endgroup$
4
  • $\begingroup$ Space partitioning is definitely better than brute force, the only hard part is choosing the right number of partitions. And if you correctly set up the partitions, searching for nearby points becomes quite fast (it's what I used in particle physics collision simulations). $\endgroup$
    – Silynn
    Commented Jul 1, 2014 at 19:28
  • $\begingroup$ Sounds like a clustering problem. $\endgroup$
    – user147263
    Commented Jul 1, 2014 at 21:22
  • $\begingroup$ Try K-d trees. $\endgroup$
    – Hao Ye
    Commented Jul 2, 2014 at 2:39
  • $\begingroup$ @HaoYe According to Wikipedia: k-d trees are not suitable for efficiently finding the nearest neighbour in high-dimensional spaces. The space I'm working with is extremely high-dimensional. Is there an effective clustering method for high-dimensional space? $\endgroup$
    – UnknownUser
    Commented Jul 2, 2014 at 5:51

0

Reset to default

You must log in to answer this question.