0
$\begingroup$

Does there exists an data structure that stores in a dictionary vectors, then when given a key that is also a vector returns the k nearest vectors using a similarity like Euclidean or Cosine? Something computationally efficient would be ideal.

$\endgroup$
2
$\begingroup$

What you're describing is also a critical step in the k-nearest-neighbours method. So no need to reinvent the wheel, we can just look how other people have sped up that algorithm.

I don't know about any dictionary like structure that returns this directly, but you could use a k-d tree. If properly implemented, you can get the k closest vectors pretty quickly.

This question might also be interesting.

$\endgroup$
4
  • $\begingroup$ do you think this would suffice for 2000 vectors of 512 dimensions? $\endgroup$ – user8714896 Feb 17 at 8:31
  • $\begingroup$ yeah, probably, you could also search for libraries that implement k-nearest-neighbours for extra speed. $\endgroup$ – Thijs Steel Feb 17 at 18:26
  • 1
    $\begingroup$ 512 dimensions seems too large for a kd-tree. After all, you would have 2^512 possible orthants to organize 2000 data points. $\endgroup$ – Charlie S Feb 19 at 16:11
  • $\begingroup$ Hmmm, that is true. I was focused on the 2000, not the dimension. I still think some space dividing structure will work, but a kd-tree is indeed not ideal $\endgroup$ – Thijs Steel Feb 19 at 16:21

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.