K-D Tree против R-Tree для небольших динамических данных

Я читал несколько сообщений SO о деревьях KD и R-деревьях, но у меня все еще есть некоторые вопросы относительно моего конкретного приложения.

Для моего Java-приложения я хочу поддерживать относительно небольшое количество точек пространственных данных (несколько сотен тысяч). Ключевым моментом является то, что вставка данных не будет загружаться массово, а будет вставляться часто и поэтапно. Я также должен упомянуть, что я буду выполнять большое количество периодических запросов диапазона в подобластях пространственной области.

Я читал, что деревья K-D обычно не поддерживают инкрементное построение и что R-деревья больше подходят для этого, поскольку они поддерживают сбалансированное состояние.

Однако после изучения предложенных здесь решений: коммерческая реализация R-tree для Java?< /а>

Я не обнаружил, что с реализациями было легко работать для возврата списка точек при поиске по диапазону. Однако я обнаружил: http://java-ml.sourceforge.net/ для очень хорошая реализация дерева KD, которое работает быстро и превосходит стандартное хранилище массивов для тестового набора точек (~ 25 КБ). Кроме того, я читал, что R-деревья хранят избыточную информацию при работе с точками (поскольку точка представляет собой прямоугольник с min=max).

Поскольку я работаю с меньшим числом точек, являются ли различия между двумя структурами менее важными, чем, скажем, если бы я работал с приложением базы данных, хранящим миллионы точек?


java r-tree kdtree
person Nathaniel Wendt    schedule 01.02.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Неверно, что R-деревья не могут хранить очки. Они предназначены для поддержки прямоугольников и должны делать это во внутренних узлах. Но хорошая реализация должна хранить точки на уровне листа и иметь там примерно двойную емкость данных.

Вы можете тривиально сохранить точки и представить их как "прямоугольники" с min=max для кода управления деревом.

Ваши данные не малы. Небольшой будет как 100 объектов. Для 100 объектов R-дерево не имеет особого смысла, так как оно, скорее всего, будет состоять только из одного листа. Для хорошей производительности R-дерево нуждается в хорошем разветвлении. k-d-дерево всегда имеет разветвление 2; они являются бинарными деревьями. При 100 тыс. объектов k-d-дерево будет довольно глубоким. Предполагая, что у вас разветвление 100 (для динамических r-деревьев вы должны разрешить до 200 объектов на страницу), вы можете хранить 1 миллион точек в 3-уровневом дереве.

Я использовал ELKI R*-дерево, и это очень быстро. Но это некоммерческий подход, если только вы не получите другую лицензию: это лицензия AGPL-3, которая является лицензией с авторским левом.

Кроме того, API не предназначен для автономного использования. Если вы хотите их использовать, лучше всего работать с полным фреймворком ELKI, а не пытаться вырвать R*-дерево.

Если ваши данные низкоразмерные (скажем, трехмерные) и имеют конечную границу, не стоит недооценивать эффективность простых подходов на основе сетки. В частности, для операций в памяти. Во многих случаях я бы даже не стал обращаться к октодереву, а просто определил бы оптимальную сетку для моего варианта использования, а затем реализовал бы ее с помощью списков объектов. Сохраняйте сортировку по одной координате в каждой ячейке сетки, чтобы еще больше повысить производительность.

person Has QUIT--Anony-Mousse    schedule 01.02.2014
comment
Границы моего региона не известны априори и могут быть изменены при добавлении данных. Считаете ли вы, что грид-подходы заслуживают изучения, если они должны адаптироваться к росту доступной грид-системы? - person Nathaniel Wendt; 03.02.2014
comment
Пока у вас есть некоторое представление о границах, грид-подходы могут работать хорошо, если вы спроектируете свою сетку так, чтобы она могла расти в любом направлении (например, разрешая отрицательные индексы и сохраняя только занятые ячейки сетки). - person Has QUIT--Anony-Mousse; 03.02.2014
comment
какие простые подходы на основе сетки можно использовать? - person nicodjimenez; 17.11.2014
comment
Зависит от ваших данных. Попробуйте 10-100 ячеек сетки в каждом измерении. Линейное сканирование в ячейке сетки точек, а затем в соседних ячейках сетки, пока вы не сможете полностью их обрезать. - person Has QUIT--Anony-Mousse; 17.11.2014

arrow_upward
1
arrow_downward

Если вы хотите часто добавлять/удалять/обновлять точки данных, вы можете посмотреть PH-дерево. Доступна версия Java с открытым исходным кодом: www.phtree.org

Он немного похож на дерево квадрантов, но гораздо более эффективен за счет использования бинарных гиперкубов и совместного использования префиксов.

Он имеет отличную производительность обновления (не требует перебалансировки) и довольно эффективно использует память. Он лучше работает с большими наборами данных, но 100 000 должно подойти для 2 или 3 измерений.

person TilmannZ    schedule 25.10.2015