I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also I've read that in general, all space-partitioning data structures tends to perform exhaustive search with high dimensional data.  Additionally, there are two important facts to be considered (ordered by  relevance):Precision: The nearest neighbors must be found (not approximations).Speed: The search must be as fast as possible. (The time to create the data structure isn't really important).So, I need some advice about:The data structure to perform kNN.If it will be better to use an aNN (approximate nearest neighbor) approach, setting it as accurate as possible?.
Best data structure for high dimensional nearest neighbor search
data structures;approximation;efficiency;nearest neighbour