4551
правка
R-дерево: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
Теорема 1 ([1, 12]). Имеется множество из N точек в пространстве <math>\mathbb{R}_d \;</math>, такое, что для любого R-дерева T, построенного на этих точках, существует пустой оконный запрос, для выполнения которого алгоритм запроса должен посетить Z2((N/B)1-lld) вершин T. | Теорема 1 ([1, 12]). Имеется множество из N точек в пространстве <math>\mathbb{R}_d \;</math>, такое, что для любого R-дерева <math>\mathcal{T} \;</math>, построенного на этих точках, существует пустой оконный запрос, для выполнения которого алгоритм запроса должен посетить Z2((N/B)1-lld) вершин <math>\mathcal{T} \;</math>. | ||
| Строка 43: | Строка 43: | ||
Было также отмечено, что R-деревья с приоритетами на практике работают весьма успешно [3]. Однако неизвестно, как эффективно обновлять их с сохранением границы для наихудшего случая. Для поддержки операций вставки и удаления был предложен логарифмический метод [3], однако получающаяся структура уже не будет R-деревом. Заметим, однако, что нижняя граница из теоремы 1 относится только к R-деревьям. Если структура данных не ограничена определением R-дерева, в процессе выполнения оконных запросов можно получить более подходящие границы; см., например, [4]. | Было также отмечено, что R-деревья с приоритетами на практике работают весьма успешно [3]. Однако неизвестно, как эффективно обновлять их с сохранением границы для наихудшего случая. Для поддержки операций вставки и удаления был предложен логарифмический метод [3], однако получающаяся структура уже не будет R-деревом. Заметим, однако, что нижняя граница из теоремы 1 относится только к R-деревьям. Если структура данных не ограничена определением R-дерева, в процессе выполнения оконных запросов можно получить более подходящие границы; см., например, [4]. | ||
== Применение == | == Применение == | ||