Spatial index with sum and counter for C ++
I am looking for an implementation of a spatial index that allows me to quickly count and sum the values contained in a specified area.
Longer version: I have a lot of objects that I want to store in a spatial index. Each of them has its own coordinates in n-dimensional space, as well as one additional value. Given the range, I need a quick answer to the questions (1) how many objects are within the range, and (2) what is the sum of all their values.
I know that a spatial index is usually implemented using R-trees. Of course, I could just get all the objects within the range and sum them each time.
However, there seems to be a significant speed-up opportunity by keeping the sum and count of all the elements contained in a node within that very node. That way, once the node in question is completely within the requested range, there is no need to move the tree further down.
Does anyone know of a C ++ implementation that supports such "cached" operations?
source to share
Boost has a nice R-tree implmentation , although I don't think the functionality you are looking for is built in.
One approach is to change the datatype of the node to include an extra field to represent the metadata of the subtree (the number of children and the sum of the subtree), or make the node a tuple of your current type and metadata. Whenever you add, edit, or remove a node, these functions call an update function that will traverse the chain of parent nodes, increasing or decreasing the metadata.
I suspect that if you are going to load data on load it is even easier as you can do it in just two passes, one of them to go through and calculate the metadata for each node, and then do a series of inserts that don't do the function updates.
Unless you're going in bulk, another common spatial index is quadtree . This data structure is often better suited for spatial data that is frequently updated, as it does not need to be rebalanced all the time. I use quadrants more than R-trees and find them super flexible.
source to share
So what are you thinking about is the added R-tree. Interestingly, while I imagine it will be useful for this query, the regions of the query should be quite large WRT bounding cells of nodes and values stored in the R-tree. Otherwise, the request will be forced to always check leaf nodes (but there would be service counters, additional checks).
Indeed, as Justin R. said, Boost.Geometry The R-tree implementation does not store any counters in the nodes, allows additional data stored in the nodes or user queries to be defined, at least for now (Boost 1.57).
However, this counting query could be optimized. There is no need to return any values, create and fill a temporary container, etc. Instead, the values can be calculated on the fly during a query, for example. like this in C ++ 11:
size_t counter = 0;
rtree.query(bgi::intersects(box),
boost::make_function_output_iterator(
[&](Value const&) {
counter++;
}));
source to share