r tree — Пространственный индекс с суммой и количеством для переполнения стека

Question

r tree — Пространственный индекс с суммой и количеством для переполнения стека

Я ищу реализацию пространственного индекса, который позволяет мне быстро подсчитывать и суммировать значения, которые содержатся в указанной области.

Более длинная версия:
У меня есть много объектов, которые я хочу сохранить в пространственном индексе. У каждого из них есть свои координаты в n-мерном пространстве, а также одно дополнительное значение. Учитывая диапазон, мне нужен быстрый ответ на вопросы: (1) сколько объектов находится в пределах диапазона и (2) какова сумма всех их значений.

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

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

Кто-нибудь знает реализацию C ++, которая поддерживает такие «кэшированные» операции?

3

c++r-tree

Решение

Другие решения

Так что вы думаете о расширенном R-дереве. Интересно, хотя я предполагаю извлечь выгоду из этого дополнения, регионы запросов должны были бы быть довольно большими WRT ограничивающими рамками узлов и значений, хранящихся в R-дереве. В противном случае запрос будет по-прежнему всегда проверять конечные узлы (но это может привести к дополнительным расходам — счетчикам, дополнительным проверкам).

Действительно, как сказал Джастин Р. Boost.Geometry Реализация R-дерева не хранит счетчики в узлах, позволяет определять дополнительные данные, хранящиеся в узлах или пользовательских запросах, по крайней мере, на данный момент (Boost 1.57).

Однако можно было бы оптимизировать этот счетный запрос. Не требуется возвращать какие-либо значения, создавать и заполнять временный контейнер и т. Д. Вместо этого значения могут быть подсчитаны на лету во время запроса, например, как это в C ++ 11:

size_t counter = 0;
rtree.query(bgi::intersects(box),
boost::make_function_output_iterator(
[&](Value const&) {
counter++;
}));

1

Источник

Accepted Answer

Boost имеет хороший Имплантация R-дерева, хотя я не думаю, что функциональность, которую вы ищете, является встроенной.

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

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

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

3