Does there exists a data structure with these properties

  1. Stores vectors in a dictionary
  2. When given a key that is also a vector, returns the k nearest vectors using a similarity metric (e.g. Euclidean, Cosine)?

Something computationally efficient would be ideal.


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.

  • $\begingroup$ do you think this would suffice for 2000 vectors of 512 dimensions? $\endgroup$ Feb 17 '21 at 8:31
  • $\begingroup$ yeah, probably, you could also search for libraries that implement k-nearest-neighbours for extra speed. $\endgroup$ Feb 17 '21 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 '21 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$ Feb 19 '21 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.