0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tassle
    Nov 20 '19 at 0:54
  • $\begingroup$ 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. $\endgroup$
    – Saku
    Nov 20 '19 at 7:59
1
$\begingroup$

If you don't want the exact nearest neighbour but would be satisfied with finding points that are not too far off, then you should take a look at Approximate nearest neighbour search.

Wikipedia suggests the following approaches:

Depending on the distribution of your data, not all dimensions may be equally relevant (maybe all points are bunched together along some line or hyperplane) and you could also use dimensionality reduction techniques, the main one being PCA (or maybe autoencoders nowadays).

Of course you can combine both, and that is also what I would recommend you to do in most cases.

If you want the exact nearest neighbour, unfortunately research suggests that this is very hard in high dimensions (see curse of dimensionality), and with a 512 dimensional space "clever" methods can very well end up being worse in practice than simply searching through all points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.