выбор параметров для R* Tree с помощью библиотеки SpatialIndex

Я использую библиотеку пространственного индекса из http://libspatialindex.github.com/.

Я создаю дерево R * в основной памяти:

size_t capacity = 10;
bool bWriteThrough = false;
fileInMem = StorageManager
    ::createNewRandomEvictionsBuffer(*memStorage, capacity, bWriteThrough);

double fillFactor = 0.7;
size_t indexCapacity = 10;
size_t leafCapacity = 10;
size_t dimension = 2;
RTree::RTreeVariant rv = RTree::RV_RSTAR;
tree = RTree::createNewRTree(*fileInMem, fillFactor, indexCapacity,
   leafCapacity, dimension, rv, indexIdentifier);

Затем я вставляю большое количество ограничивающих прямоугольников, в настоящее время около 2,5 млн (дорожная сеть Баварии в Германии). Позже постараюсь вставить все дороги Европы.

Каков хороший выбор параметров для менеджера хранилища и rtree? В основном я использую rtree для поиска ближайших дорог к заданному запросу (пересечение bbox).


c++ indexing spatial-index spatial r-tree
person arthur    schedule 25.10.2012    source источник
comment
+1 Потому что я никогда раньше не слышал о R*-дереве, а это довольно интересно. en.wikipedia.org/wiki/R*_tree   -  person John Dibling    schedule 25.10.2012
comment
Ну, это довольно стандартная структура индекса, используемая для ответа на запросы пространственного диапазона (дайте мне все объекты, которые попадают в заданный запрос прямоугольника) и запросы ближайшего соседа (дайте мне k объектов, ближайших к моему точечному запросу). Если вам интересно, взгляните на пространственные индексы в целом: en.wikipedia.org/wiki/Spatial_database< /а>   -  person arthur    schedule 25.10.2012

Ответы (1)


arrow_upward
3
arrow_downward

Поскольку ваши данные статичны, вам может подойти хорошая массовая загрузка. Самая популярная (и довольно простая) блук-загрузка — Sort-Tile-Recursive. Тем не менее, он в некоторой степени разработан для точечных данных. Когда вы вставляете пространственные объекты, это может работать или не работать.

Если вы используете массовую загрузку, это будет уже не R*-дерево, а обычное R-дерево.

Емкость 10 кажется мне намного малой. Вам нужен гораздо больший разветвитель. Но вам нужно будет сравнить, это зависит от набора данных и запроса, что хорошо. Я бы определенно попробовал 100 или больше.

person Has QUIT--Anony-Mousse    schedule 04.11.2012
comment
Спасибо за комментарии и информацию. Я уже увеличил оба значения емкости до 100. Это строит дерево высотой 3. Я попытаюсь поэкспериментировать со значениями и опубликую их здесь через несколько дней. - person arthur; 05.11.2012
comment
Согласно тому, что Марио объяснил в lists.gispython.org/pipermail/spatialindex/ 2013 — июнь/, дерево с массовой загрузкой не является ни простым R-деревом, ни R*-деревом. - person mloskot; 10.06.2013
comment
Тогда эта почта неточна. Массовая загрузка R-дерева с помощью STR не создаст точно такое же дерево, как при инкрементной загрузке R-дерева (по понятным причинам, например, скорость заполнения намного выше, чем при инкрементной загрузке дерева), но, тем не менее, это правильное R-и R*-дерево, и его можно как запрашивать, так и обновлять одним и тем же способом. - person Has QUIT--Anony-Mousse; 10.06.2013