[Spatialindex] RTree::deleteData() very expensive
mhadji at gmail.com
Tue May 15 17:44:01 EEST 2012
Hi Matthias. The R-star strategy has expensive inserts. You can use
the Linear insertion algorithm instead, which is much faster but
results in a slightly less well organized tree structure.
There is nothing you can do to speed up deletes. A delete has cost
equal to a point location query, followed by possible reorganization
to keep the tree balanced. You would have to implement an R-tree with
update memos or similar strategies.
Generally speaking, R-trees are not the right index structure for
keeping track of moving objects, especially in main memory (it is well
known that they have lousy update performance). Use a hierarchical
grid instead. If you need to store the index in secondary storage, use
a grid file.
On Tue, May 15, 2012 at 5:35 AM, <MSattler at spirit21.de> wrote:
> Hallo folks,
> currenty I'm evaluating libspatialindex 1.7.1. I'm working on comparingly
> small datasets in memory. There are a few 100000s of static objects and a
> few 1000s of objects that move around. Updating the moving objects in the
> index takes a lot of compute time, so there is little compute time left for
> the rest. I update the objects by removing and reinserting them at the new
> position. RTree::deleteData() is a bit more expensive than
> Do you have an idea what I can do?
> Maybe using different creation parameters of the RTree?
> Or is there a quicker way to update the position of the moving objects?
> Currently I'm creating the RTRee like that:
> SpatialIndex::RTree::createNewRTree(storageManager, 0.7, 30, 30, 3,
> SpatialIndex::RTree::RV_RSTAR, identifier);
> Spatialindex mailing list
> Spatialindex at lists.gispython.org
More information about the Spatialindex