Finding smallest angle between vectors in logarithmic time

Question

I have n=10000 10-dimensional vectors. For every vector v1 I want to know the vector v2 that minimizes the angle between v1 and v2.

Is there a way to solve this problem faster than O(n^2)?

Answer 1

You can normalize all the vectors in O(n) time and find a parameterization of them onto the resulting 9-dimensional hypersphere. You can then use a spatial search structure in the n-1 dimensional space, like a Kd-tree to speed up the nearest neighbor query. There are well known methods (ANN) to do this.