k-вимірне дерево

В інформатиці k-d дерево (англ. k-d tree, скорочення від k-вимірне дерево) — це структура даних з поділом простору для упорядкування точок в k-вимірному просторі. K-d дерева використовуються для деяких застосувань, таких як пошук у багатовимірному просторі ключів (пошук діапазонів^[en] і пошук найближчого сусіда). K-d дерева — особливий вид дерев двійкового поділу простору.

Математичний опис[ред. | ред. код]

K-вимірне дерево — це незбалансоване дерево пошуку для зберігання точок з $\mathbb {R} ^{k}$ . Воно пропонує схожу на R-дерево можливість пошуку в заданому діапазоні ключів. На шкоду простоті запитів, вимоги до пам'яті $~O(kn)$ замість $~O((\log(n))^{k-1})$ .

Існують однорідні й неоднорідні k-d дерева. В однорідних k-d дерев кожен вузол зберігає запис. При неоднорідному варіанті внутрішні вузли містять тільки ключі, листя містить посилання на записи.

У неоднорідному k-d дереві $H_{i}(t)=(x_{1},x_{2},\ldots ,x_{i-1},t,x_{i+1},\ldots ,x_{k})$ при $1\leq i\leq k$ паралельно осі $(k-1)$ -мірної гіперплощини в точці $t$ . Для кореня потрібно розділити точки через гіперплощину $H_{1}(t)$ на дві по можливості однаково великі безлічі точок і записати $t$ в корінь, ліворуч від цього зберігаються всі точки, у яких $x_{1}<t$ , праворуч ті, у яких $x_{1}>t$ . Для лівого піддерева потрібно розділити точки знову на нову «розділену площину» $H_{2}(t)$ , а $t$ зберігається у внутрішньому вузлі. Зліва від цього зберігаються всі точки, у яких $x_{2}<t$ . Це триває рекурсивно над усіма просторами. Потім все починається знову з першого простору, доки кожну точку можна буде ясно ідентифікувати через гіперплощину.

K-d дерево можна побудувати за $~O(n(k+\log(n)))$ . Пошук діапазону можна виконати за $~O(n^{1-{\frac {1}{k}}}+a)$ , при цьому $a$ позначає розмір відповіді. Вимогу до пам'яті для самого дерева обмежено $~O(kn)$ . ^[1]

Операції з k-d деревами[ред. | ред. код]

Структура[ред. | ред. код]

Структура дерева, описана на мові C ++:

const N = 10; // Кількість просторів ключів

struct Item {// структура елемента
  int key [N]; // Масив ключів визначає елемент
  char * info; // Інформація елемента
};

struct Node {// структура вузла дерева
  Item i; // Елемент
  Node * left; // Ліве піддерево
  Node * right; // Праве піддерево
}

Структура дерева може змінюватись в залежності від деталей реалізації алгоритму. Наприклад, у вузлі може міститися не один елемент, а масив, що підвищує ефективність пошуку.

Аналіз пошуку елемента

Очевидно, що мінімальна кількість переглянутих елементів дорівнює $1$ , а максимальна кількість переглянутих елементів — $~O(h)$ , де $h$ — це висота дерева. Залишається порахувати середню кількість переглянутих елементів $A_{n}$ .

$[x_{0},x_{1},x_{2},...,x_{n}]$ — заданий елемент.

Розглянемо випадок $h=3$ . Знайденими елементами можуть бути:

find(t_{1}):[(x_{0}=t_{1})];A=1.

find(t_{2}):[(x_{0}<t_{1})\land (x_{0}=t_{2})];A=2.

find(t_{3}):[(x_{0}>t_{1})\land (x_{0}=t_{3})];A=2.

find(t_{4}):[(x_{0}<t_{1})\land (x_{0}<t_{2})\land (x_{0}=t_{4})];A=3.

find(t_{5}):[(x_{0}<X_{1})\land (x_{0}>t_{2})\land (x_{0}=t_{5})];A=3.

find(t_{6}):[(x_{0}<t_{1})\land (x_{0}<t_{3})\land (x_{0}=t_{6})];A=3.

find(t_{7}):[(x_{0}<t_{1})\land (x_{0}>t_{3})\land (x_{0}=t_{7})];A=3.

і так для кожного простору ключів. При цьому середня довжина пошуку в одному просторі становить:

A={\frac {1+2+2+3+3+3+3}{7}}={\frac {17}{7}}\approx 2,4

.

Середня величина розраховується за формулою: $A_{n}=\sum _{k=1}^{n}kp_{n,k}$

Залишається знайти ймовірність $p_{n,k}$ . Вона дорівнює $p_{n,k}={\frac {p_{A,k}}{p_{n}}}$ , де $p_{A,k}$ — число випадків, коли $A=k$ , і $p_{n}$ — загальне число випадків.

Не складно здогадатись, що $p_{n,k}={\frac {2^{k-1}}{2^{n}-1}}$

Підставляємо це в формулу для середньої величини:

A_{n}=\sum _{k=1}^{n}kp_{n,k}=\sum _{k=1}^{n}{k{\frac {2^{k-1}}{2^{n}-1}}}={\frac {1}{2^{n}-1}}\sum _{k=1}^{n}{k2^{k-1}}=

={\frac {1}{2^{n}-1}}\sum _{k+1=1}^{n}{({k+1})2^{k}}={\frac {1}{2^{n}-1}}(\sum _{k+1=1}^{n}{k2^{k}}+\sum _{k+1=1}^{n}{2^{k}})=

={\frac {1}{2^{n}-1}}\left(\sum _{k=1}^{n}{k2^{k}}+\sum _{k=1}^{n}{2^{k}}-2^{n}-n2^{n}\right)=

={\frac {1}{2^{n}-1}}(n2^{n+2}-(n+1)2^{n+1}+2-2^{n}+2^{3}-1-n2^{n})={\frac {2^{n}(n-1)+1}{2^{n}-1}}

тобто, $A_{h}={\frac {2^{h}(h-1)+1}{2^{h}-1}}$ , де $h$ — висота дерева.

Якщо перейти від висоти дерева до кількості елементів, то:

A_{n}=~O\left({\frac {2^{h}(h-1)+1}{2^{h}-1}}\right)=~O\left(h{\frac {2^{h}}{2^{h}-1}}-1\right)=~O\left(\log \left({\frac {n}{N}}+1\right){\frac {2^{\log({\frac {n}{N}}+1)}}{2^{\log({\frac {n}{N}}+1)}-1}}-1\right)=~O\left(\log \left({\frac {n}{N}}+1\right){\frac {n+N}{n}}-1\right)=

$=~O\left(\log \left({\frac {n}{N}}+1\right)^{\frac {n+N}{n}}-1\right)$ , де $N$ — кількість елементів у вузлі.

З цього можна зробити висновок, що чим більше елементів буде міститись у вузлі, тим швидше буде проходити пошук по дереву, оскільки висота дерева залишатиметься мінімальною, проте не слід зберігати величезну кількість елементів у вузлі, оскільки при такому способі все дерево може дегенерувати у звичайний масив або список.

Додавання елементів[ред. | ред. код]

Додавання елементів відбувається точно так само, як і в звичайному двійковому дереві пошуку, з тією лише різницею, що кожен рівень дерева буде визначатися ще й простором, до якого він відноситься.

Алгоритм просування по дереву:

for (int i = 0; tree; i ++) // i - це номер простору
    if (tree-> x [i] <tree-> t) // t - медіана
        tree = tree-> left; // Переходимо в ліве піддерево
    else
        tree = tree-> right; // Переходимо в праве піддерево

Додавання виконується за $~O(h)$ , де $h$ — висота дерева.

Видалення елементів[ред. | ред. код]

При видаленні елементів дерева може виникнути декілька ситуацій.

Видалення листа дерева — досить просте видалення, коли видаляється один вузол, і покажчик вузла-предка просто обнуляється.^[2]

Видалення вузла дерева (не листа) — дуже складна процедура, при якій доводиться перебудовувати все піддерево для даного вузла.

Іноді процес видалення вузла вирішується модифікаціями k-d дерева. Наприклад, якщо у нас у вузлі міститься масив елементів, то при видаленні всього масиву вузол дерева залишається, але нові елементи туди більше не записуються.

Пошук діапазону елементів[ред. | ред. код]

Пошук заснований на звичайному спуску по дереву, коли кожен вузол перевіряється на діапазон. Якщо медіани вузла менше або більше заданого діапазону в даному просторі, то обхід йде далі по одній з гілок дерева. Якщо ж медіана вузла входить повністю в заданий діапазон, то потрібно відвідати обидва піддерева.^[3]

Алгоритм

Z - вузол дерева
[(X_0_min, x_1_min, x_2_min, ..., x_n_min), (x_0_max, x_1_max, x_2_max, ..., x_n_max)] - заданий діапазон

Функція Array (Node * & Z) {
If ([x_0_min, x_1_min, x_2_min, ..., x_n_min] <Z) {
Z = Z-> left; // Ліве піддерево
}
else
If ([x_0_max, x_1_max, x_2_max, ..., x_n_max]> Z) {
Z = Z-> right; // Праве піддерево
}
Else {// переглянути обидва піддерева
Array (Z-> right); // Запустити функцію для правого піддерева
Z = Z-> left; // Переглянути ліве піддерево
}
}

Аналіз

Очевидно, що мінімальна кількість переглянутих елементів це $~O(h)$ , де $h$ — висота дерева. Так само очевидно, що максимальна кількість переглянутих елементів це $~O(2^{h}-1)$ , тобто перегляд всіх елементів дерева. Залишається порахувати середню кількість переглянутих елементів $A_{n}$ .

$[(x_{0_{min}},x_{1_{min}},x_{2_{min}},...,x_{n_{min}}),(x_{0_{max}},x_{1_{max}},x_{2_{max}},...,x_{n_{max}})]$ — заданий діапазон.

Оригінальна стаття про k-d дерева дає таку характеристику: $A_{n}=~O(h\cdot \log(h))$ для фіксованого діапазону.

Якщо перейти від висоти дерева до кількості елементів, то це буде: $A_{n}=~O(\log(\log(n-1))^{\log(n-1)})$

Пошук найближчого сусіда[ред. | ред. код]

Пошук найближчого елемента розділяється на дві підзадачі:

1) визначення можливого найближчого елемента;

2) пошук найближчих елементів в заданому діапазоні.

Анімація NN пошука с a k-d дерева в двох масивах

Дано дерево $tree$ . Ми спускаємося по дереву до його листа за умовою $tree\to x[i](<,>=)tree\to t$ і визначаємо ймовірний найближчий елемент за умовою $l_{min}={\sqrt {(({x_{0}-x[i]_{0}})^{2}+({x_{1}-x[i]_{1}})^{2}+...+({x_{n}-x[i]_{n}})^{2})}}$ . Після цього від кореня дерева запускається алгоритм пошуку найближчого елемента в заданому діапазоні, який визначається радіусом $R=l_{min}={\sqrt {(({x_{0}-x[i]_{0}})^{2}+({x_{1}-x[i]_{1}})^{2}+...+({x_{n}-x[i]_{n}})^{2})}}$ .

Радіус пошуку коригується при знаходженні найближчого елемента.^[4]

Алгоритм

Z - корінь дерева |
List - список найближчих елементів |
[X_0, x_1, x_2 ..., x_n] - елемент для якого шукаються найближчі
Len - мінімальна довжина

Функція Maybe_Near (Node * & Z) // пошук найближчого можливого елемента
{
  While (Z) 
  {
    // Перевірка елементів у вузлі
    for (i = 0; i <N; i ++) 
    {
      len_cur = sqrt ((x_0 - x[i]_0) ^ 2 + (x_1 - x[i]_1) ^ 2 + ... + (x_n - x[i]_n) ^ 2); // Довжина поточного елемента
      if (Len> довжини поточного елемента) 
      {
        Len = len_cur; // Встановлення нової довжини
        Delete (List); // Очищення списку
        Add (List); // Додати новий елемент у список
      }
      Else
        if (довжини рівні)
          Add (List); // Додати новий елемент у список
      If ((x_0 = x[i]_0) && (x_1 = x[i]_1) && ... && (x_n = x[i]_n))
        Return 1;
    }
    If ([x_0, x_1, x_2 ..., x_n] <Z)
      Z = Z-> left; // Ліве піддерево
    If ([x_0, x_1, x_2 ..., x_n]> Z)
      Z = Z-> right; // Праве піддерево
  }
}


Функція Near (Node * & Z) {// пошук найближчого елемента в заданому діапазоні
While (Z) {
// Перевірка елементів у вузлі
for (i = 0; i <N; i ++) {
len_cur = sqrt ((x_0-x [i] _0) ^ 2 + (x_1-x [i] _1) ^ 2 + ... + (x_n-x [i] _n) ^ 2); // Довжина поточного елемента
if (Len> довжини поточного елемента) {
Len = len_cur; // Встановлення нової довжини
Delete (List); // Очистка списку
Add (List); // Додати новий елемент у список
}
Else
if (довжини рівні)
Add (List); // Додати новий елемент у список
}
If ([x_0, x_1, x_2 ..., x_n] + len> Z) {// якщо діапазон більше медіани
Near (Z-> right); // Переглянути обидва дерева
Z = Z-> left;
}
If ([x_0, x_1, x_2 ..., x_n] <Z)
Z = Z-> left; // Ліве піддерево
If ([x_0, x_1, x_2 ..., x_n]> Z)
Z = Z-> right; // Праве піддерево
}
}

Аналіз

Очевидно, що мінімальна кількість переглянутих елементів це $~O(h)$ , де h — висота дерева. Так само очевидно, що максимальна кількість переглянутих елементів це $~O(2^{h}-1)$ , тобто перегляд всіх вузлів. Залишається порахувати середню кількість переглянутих елементів.

$[(x_{0},x_{1},x_{2},...,x_{n})]$ — заданий елемент, щодо якого потрібно знайти найближчий. Це завдання розділяється на дві підзадачі: знаходження найближчого елемента у вузлі й знаходження найближчого елемента в заданому діапазоні. Для вирішення першої підзадачі потрібен один спуск по дереву, тобто $~O(h)$ .

Для другої підзадачі, як ми вже вирахували, пошук елементів в заданому діапазоні виконується за $~O(h\cdot \log(h))$ . Щоб дізнатися середнє, досить просто скласти ці дві величини:

$=~O(h)+~O(h\cdot \log(h))=~O(h)\cdot ({~O(\log(h))+1}))$ .

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

↑ Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM. 18 (9): 509. doi:10.1145/361002.361007.
↑ Chandran, Sharat. Introduction to kd-trees [Архівовано 23 вересня 2015 у Wayback Machine.]. University of Maryland Department of Computer Science.
↑ Lee, D. T.; Wong, C. K. (1977). Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica. 9. doi:10.1007/BF00263763.
↑ Freidman, J. H.; Bentley, J. L.; Finkel, R. A. (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software. 3 (3): 209. doi:10.1145/355744.355745.

Зовнішні посилання[ред. | ред. код]

libkdtree ++, an open-source STL-like implementation of k — d trees in C ++.
A tutorial on KD Trees
FLANN and its fork nanoflann [Архівовано 28 грудня 2014 у Wayback Machine.], efficient C ++ implementations of k — d tree algorithms.
kdtree [Архівовано 9 січня 2015 у Wayback Machine.] A simple C library for working with KD-Trees
KD Tree Demo, Java applet [Архівовано 29 червня 2020 у Wayback Machine.]
libANN [Архівовано 15 січня 2021 у Wayback Machine.] Approximate Nearest Neighbour Library includes a k — d tree implementation
Caltech Large Scale Image Search Toolbox: a Matlab toolbox implementing randomized k — d tree for fast approximate nearest neighbour search, in addition to LSH, Hierarchical K-Means, and Inverted File search algorithms.
Heuristic Ray Shooting Algorithms [Архівовано 11 листопада 2016 у Wayback Machine.], pp. 11 and after
Into contains open source implementations of exact and approximate (k) NN search methods using k — d trees in C ++.

[1] Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM. 18 (9): 509. doi:10.1145/361002.361007.

[2] Chandran, Sharat. Introduction to kd-trees [Архівовано 23 вересня 2015 у Wayback Machine.]. University of Maryland Department of Computer Science.

[Lee1977-3] Lee, D. T.; Wong, C. K. (1977). Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica. 9. doi:10.1007/BF00263763.

[Friedman:1977:AFB:355744.355745-4] Freidman, J. H.; Bentley, J. L.; Finkel, R. A. (1977). An Algorithm for Finding Best Matches in Logarithmic Expected Time. ACM Transactions on Mathematical Software. 3 (3): 209. doi:10.1145/355744.355745.

[1]

[2]

[3]

[4]