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: Mikkel B. Stegmann (mikkel.stegmann_at_[hidden])
Date: 2013-11-11 05:46:09

Hi Adam,

thanks for your input. I've now trimmed the test and converted it back to
using actual boost 2d point instances. The build time differences remain the
same. See pdf's and code below for details (the
"SpatialIndexTrimmedUtilities.h" include is solely for the time and memory
measurements done in the brief test code). 

One thing worth noticing -- and this is entirely my bad -- the search times
are improved compared to earlier. I (wrongfully) assumed that a run time of
5-10 us was fine for a single search test, as my timings were highly
reproducible. However, there seems to be some initial cost of doing the
first search, as the search time is much lower when looking at an average
across 100 searches (which I do now). The difference between bulk/non-bulk
however, remains subtle.

As the building times are my main concern, I will try to add some jitter to
my uniform points and redo the test. (But, the problem is that my actual
application is not that far from a fairly regular grid.)

Best regards,
Mikkel

01_131111_Results_-_linear_16.pdf
<http://boost-geometry.203548.n3.nabble.com/file/n4025747/01_131111_Results_-_linear_16.pdf>  
02_131111_Results_-_linear_16,_bulk.pdf
<http://boost-geometry.203548.n3.nabble.com/file/n4025747/02_131111_Results_-_linear_16%2C_bulk.pdf>  
SpatialIndexTrimmedTest.cpp
<http://boost-geometry.203548.n3.nabble.com/file/n4025747/SpatialIndexTrimmedTest.cpp>  

--
View this message in context: http://boost-geometry.203548.n3.nabble.com/Spatial-Indexes-build-and-knn-query-performance-for-bulk-loading-packing-vs-linear-balancing-tp4025741p4025747.html
Sent from the Boost Geometry mailing list archive at Nabble.com.