Best data structure for high dimensional nearest neighbor search
Here is a closely related question (although different enough that I wouldn't call this a duplicate): https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data

As you said, all known structures degrade to linear search as the dimension grows. More specifically, the efficiency degrades as the dimension approached the number of points in the feature space (binary search doesn't help with two points, K-D trees are useless on three points, etc.).

However, if the time to create the data structure does not matter at all, you can create a complete graph with sorted edge lists. That is, every node keeps track of its neighbors in nearness order. This would take $O(n^2 \log n)$ time to create, but would give you the kNN of any point in $O(1)$.