Boost logo

Geometry :

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;

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

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


Geometry list run by mateusz at