# Searching for points near given point in a multidimensional space

I want to search many times, not identical elements but similar, for something a similar image or fingerprint without having to search the whole space. When I have a 1D case I sort it first. For 2D I can make boxes big enough to be not wasted on boxes containing no elements, these boxes have subboxes and these have elements.

There is a problem: because when the width is 100, then if I'm looking for a 401 I can find a 490 and I can't find a close element 399. You would have to look in the boxes around, in 9 instead of in one. It's still possible, but for 3D it will be 27, generally 3^n, what if we have 512D?

• Do you want the nearest neighbour or would you be satisfied with an approximation (i.e. some point that isn't too far off the nearest neighbour)? Research suggests that the first problem is very hard in high dimensions, and with a 512 dimensional space "clever" methods might actually be worse in practice than simply searching through all points. But if you are happy with approximations then there might be some hope. Nov 20 '19 at 0:54
• Fortunately not nearset neighbour but all points these aren't too far from point from first set. This algorithm should be used to map sentences from first corpus to second, Google DAN and GRU algorithms changes sentence to 512D vector and I can get similarity of two sentences, but I want map all senetences.
– Saku
Nov 20 '19 at 7:59