# Find close points by grouping points in n-dimensional space

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.

• @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? Commented Jul 2, 2014 at 5:51