Geometry Boost List: Re: [geometry] Spatial Indexes: build and knn query performance for bulk loading/packing vs. linear balancing

Subject: Re: [geometry] Spatial Indexes: build and knn query performance for bulk loading/packing vs. linear balancing
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-11-08 12:42:07

Hi Mikkel,

Mikkel B. Stegmann wrote:
> Hi Mateusz,
>
> ah, I see. And agree. My labeling might be confusing. It solely relates to
> the template parameters given to the tree type that I have used for both
> experiments in my mock-up test code:
>
> Type definition:
>
>     typedef boost::geometry::index::rtree< const T*,
> boost::geometry::index::linear<16> > TreeType;
>     boost::shared_ptr<TreeType> rTree_;
>
> Bulk loading usage:
>
>     rTree_ = boost::shared_ptr<TreeType>(new TreeType(elements.begin(),
> elements.end()));
>
> Linear balancing usage:
>
>     rTree_ = boost::shared_ptr<TreeType>(new TreeType());
>     rTree_->insert(elements.begin(), elements.end());
>

Thanks for the results of your benchmarks.

I've just tested 2d points using our benchmark and got different 
results. The building is indeed slightly slower but not as much as in 
your case (>2x). Furthermore, in my case knn query is 4x faster and box 
query is 8x faster.

In case you'd like to run my benchmark on your machine. I'm using 
libs/geometry/index/example/benchmark_experimental.cpp. Unfortunately I 
was forced to modify it:
1. For points comment #define BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
2. Copy knn test to perform it also for bulk loading

If you're unable to send the code of your benchmark maybe you could 
answer the following questions:

Probably the most important ones are:
What your data looks like exactly?
E.g. do you generate points row by row in a uniform grid with a constant 
step?
Could you try to randomize points in the grid's area, instead of 
generating a uniform grid?

But I'm also curious about the following if the above doesn't change 
anything:
What is your T?
How big it is?
How do you access coordinates?
What do your indexable_getter looks like?
Could you store your points directly, not by use of pointer?

Regards,
Adam