Boost logo

Geometry :

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


Geometry list run by mateusz at loskot.net