Как эффективно найти k-ближайших соседей в многомерных данных?

Итак, у меня есть около 16 000 75-мерных точек данных, и для каждой точки я хочу найти ее k ближайших соседи (используется евклидово расстояние, в настоящее время k = 2, если это упрощает задачу)

Моей первой мыслью было использовать для этого kd-дерево, но, как оказалось, они становятся довольно неэффективными по мере роста числа измерений. В моем примере реализации он лишь немного быстрее, чем исчерпывающий поиск.

Моей следующей идеей было бы использовать PCA (анализ главных компонентов) для уменьшения количества измерений, но мне было интересно: Есть ли какой-нибудь умный алгоритм или структура данных, чтобы решить эту проблему точно в разумные сроки?