Geometry Boost List: Re: [geometry] [index] r-tree concerns

Subject: Re: [geometry] [index] r-tree concerns
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2012-08-25 21:16:30

> feverzsj wrote:
> W dniu 2012-06-23 08:13, feverzsj napisal(a):
>> hi, Adam
>>  > 1. Should MAX and MIN be compile-time? rtree.v2.01 took run-time
>> MAX and
>>  > MIN. It was just a little slower but took more space than the current
>>  > one because static size nodes were unable to use (vectors takes more
>>  > space). But what are real-life use cases?
>> If there is only slight impact on performance, I think a more dynamic
>> way would be prefered for lib usage.
>> The template <Max Min> can be still present for convenience, e.g.:
>> template<..., int Max = defaultMax, int Min, defaultMin>
>> struct rtree
>> {
>>      rtree(..., int max_ = Max, int min_ = Min );
>> };
>
> If someone want to use the most optimized version he should be able to
> use it. So the best thing to do will be providing two interfaces.
> Something you've proposed. Internally it isn't a problem because my
> implementation allows using of various types of nodes. But I don't know
> if it should look the way you've proposed because the user wouldn't know
> which values are used by the rtree. But maby something like this:
>
> rtree<Value, AlgoStaticParams<Max, Min>, UseStatic>
>    t(AlgoDynamicParams(max, min));
>

Ok, I've implemented compile- and run-time R-tree parameters. 
Compile-time are passed as template parameters. Run-time are passed in 
the constructor:

namespace bgi = boost::geometry::index;

//compile-time
bgi::rtree<Val, bgi::linear<32, 8> > t1;
bgi::rtree<Val, bgi::quadratic<32, 8> > t2;
bgi::rtree<Val, bgi::rstar<32, 8> > t3;

//run-time
bgi::rtree<Val, bgi::runtime::linear>
   t4(bgi::runtime::linear(32, 8));
bgi::rtree<Val, bgi::runtime::quadratic>
   t5(bgi::runtime::quadratic(32, 8));
bgi::rtree<Val, bgi::runtime::rstar>
   t6(bgi::runtime::rstar(32, 8));

Of course run-time version is slower. Test results for MaxElements=32, 
MinElements=8 are below.

Inserting of 1M random 2d boxes (double):

             compile-time    run-time
linear         1.98s          2.19s
quadratic      3.33s          3.62s
rstar         25.85s         26.35s

100k intersects() queries:

             compile-time    run-time
linear          0.89s         0.97s
quadratic       0.29s         0.39s
rstar           0.14s         0.16s

10k 5 nearest neighbours queries:

             compile-time    run-time
linear          0.34s         0.39s
quadratic       0.16s         0.22s
rstar           0.09s         0.09s

Regards,
Adam