Алгоритм массовой загрузки для дерева MX-CIF - PullRequest
Новая
       39

Алгоритм массовой загрузки для дерева MX-CIF

4 голосов
/ 05 августа 2011

Мое приложение загружает коллекцию из ~ 100 тыс. Элементов (прямоугольников) из файла карты, а затем создает квадродерево MX-CIF в качестве индекса для быстрого поиска. Дерево quadtree создается при запуске, и его содержимое не изменяется во время выполнения.

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

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

Во втором проходе я добавляю каждый элемент в наименьший узел, который его полностью содержит. Как только узел проходит определенное количество элементов, он разделяется, и дочерние элементы перераспределяются между новым родительским и 4 дочерними узлами.

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

1 Ответ

0 голосов
/ 06 февраля 2015

Вам действительно нужно дерево MX-CIF?Для прямоугольников я бы предложил использовать X-Tree или PH-Tree.

X-деревья получены из R-деревьев и имеют отличное время вставки, если вы заранее знаете весь набор данных (массовая загрузка).Они также имеют очень хорошую производительность запросов диапазона.Пример реализации можно найти здесь: Библиотека XXL

PH-дерево немного медленнее при массовой загрузке, но намного быстрее, если объекты обновляются / перемещаются впоследствии.Производительность запросов диапазона похожа на X-дерево, но PH-дерево быстрее при извлечении небольших наборов результатов (основные затраты заключаются в извлечении значений, в то время как для X-дерева основные затраты заключаются в обработке запроса (поиск первого узла)....)).Реализация PH-дерева доступна здесь: PH-Tree

Отказ от ответственности: Я принимал участие в разработке PH-дерева.

...