Computer Science Asked by Saku on February 20, 2021
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?
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.
Answered by Tassle on February 20, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP