Преимущества использования KD-дерева для поиска ближайших соседей:

• Быстрое построение. 23 Поскольку разбиение выполняется только по осям данных, не требуется вычислять D-мерные расстояния. 2
• Меньшее количество вычислений расстояния. 3 После построения ближайший сосед точки запроса может быть определён только с помощью O(log(N)) вычислений расстояния. 2

KD-дерево рекурсивно разбивает пространство параметров по осям данных, разделяя его на вложенные ортотропные области, в которые подаются точки данных. 2

Однако подход KD-дерева очень быстр для поиска соседей в низкой размерности (D<20), но становится неэффективным, когда D становится очень большим. 2