Каков наилучший вариант дерева R

Question

Я недавно читал документы и коды на R-дереве и его вариантах: линейный, квадратичный, R * -tree, а также упаковка дерева R (STR). Мне кажется, что разные методы отличаются во времени сложностями создания деревьев, поиска диапазона и поиска knn. Дерево STR выглядит лучше других. Тем не менее, бумаги были из прошлого века. Мне просто интересно после почти 20 лет, каков наилучший вариант R-дерева в настоящее время?

Answer 1

R * -trees доказали свою эффективность и продолжают оставаться подходящим вариантом.

Нагрузочные методы, такие как STR, являются отличным дополнением к исходному начальному дереву быстрее (и лучше) вместо того, чтобы вставлять объекты по одному.

Как правило, вам понадобится R * -tree с нагрузкой STR.

Answer 2

Еще одно новое дерево - это X-tree (также основано на R-Tree).

Если вы ищете общую пространственную индексацию, а не только R-деревья, я могу рекомендовать PH-Tree. Он может легко конкурировать с вариантами R-Tree для прямоугольников или диапазонов запросов, имеет неплохую поддержку kNN-запросов (всего на 50% медленнее, чем Cover-Tree для 21 размера), он очень хорошо масштабируется с большими и/или кластерными наборами данных и достаточно эффективное пространство. Лучше всего, наверное, что он имеет отличную производительность обновления, вставка/перемещение/удаление занимает чуть больше времени, чем поиск. Другим преимуществом является то, что он не требует перебалансировки, а это означает, что любое обновление влияет не более чем на два узла.

Недостатки:

• Осуществление является довольно сложным, но если вы хорошо с реализацией Java, here is mine (ограниченные до 60 размеров).
• Я бы не рекомендовал его для небольших наборов данных, я бы предложил его для записи не менее 100 тыс., Лучше миллион или более.
• В основном он предпочитает кластеризованные данные, но производительность по-прежнему сохраняется с более равномерно распределенными данными.