Дерево UB

UB-дерево — збалансоване дерево для ефективного пошуку та вилучення з багатовимірних даних.

Двовимірний ^[en].

Структура

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

Вставка, видалення та точковий запит виконуються так само, як і в звичайних B⁺-деревах.

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

Історія

UB-дерево було запропоновано Рудольфом Баєром та Фолкером Марклем.

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

Примітки