Geometry Boost List: [ggl] rtree - remove

Subject: [ggl] rtree - remove
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-05-05 09:45:48

Adam Wulkiewicz wrote:
> Hi,
>
> I'm currently implementing algorithm removing element from the tree. In
> general it looks as follows:
>
> 1. Traverse the tree in order to find the leaf containing the element
> 2. Traverse back to the root deleting nodes which has less than min
> number of elements and adjusting parent's boxes
> 3. Storing the elements removed from those nodes to reinsert them later
> 4. Reinsert those elements
>
> If element were retrieved from leaf node, it's a value. If it were
> retrieved from some internal node on some level, it is a node on
> level+1. Internal node is a root of a subtree containing nodes structure
> and leafs with values.
>
> In the original algorithm [Gut84] elements retrieved from node on some
> level (e.g. some internal nodes) are reinserted to the tree and placed
> in the level where they belong. Values are of course inserted in leafs.
>
> But in the old implementation different algorithm is used. All values
> are retrieved from leaf and all retrieved nodes' subtrees. Then those
> all values from all deleted subtrees are reinserted to the tree one by one.
>
> Is there some reason, why this is done this way?
>
> [Gut84] A. Guttman - R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL
> SEARCHING.

I've implemented remove algorithm. It's an implementation of the 
original algorithm so it's different than the old one. Trees produced by 
both implementations are different. I only tested it for max:32 min:8 
and it's a lot faster. Removing 0.5M values from tree containing 1M 
takes 3.6s instead of 23.5s(old implementation).

Regards,
Adam