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.
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.