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

Subject: [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-08 03:55:28

Hi All,

I'm having a hard time finding all of the expected benefits of the,
otherwise very promising, bulk loading/packing feature added to the Boost
v1.55beta.

For a synthetic setup of 1 million points placed in a square uniform grid I
see the following characteristics for bulk loading vs. linear balancing (the
query was knn; k==1):

Build time: 1.1 / 0.4 s
Query time: 4 / 5 us
Tree size: 12 / 30 MB

And for 100 million points:

Build time: 397 / 52 s
Query time: 9 / 7 us
Tree size: 1233 / 3046 MB

The environment was a 64-bit compile using gcc 4.4.7 running Ubuntu 12.04.

Although I would appreciate benefits w.r.t. query time similar to those
illustrated for boxes in [1], this remains a secondary concern. (However, as
the tree-size is markedly reduced I would assume that the improved tree
structure would translate to improved measurements. But that might be
related to the very simple spatial structure used for this synthetic
benchmark, i.e. points in a uniform grid.)

My main concern is the marked increase in build time, which again is
conflicting with the boxes case in [1]. As my usage really isn't dynamic,
the bulk loading feature should be very attractive. But at this point, I'm
not sure that I want to leverage the improvements in storage, at the expense
of a dramatic increase in build time.

Do any of you have an idea of what is in play here?

(Graphs and other grid sizes are detailed in the attached PDFs for both
cases.)

Best regards,
Mikkel B. Stegmann

[1] 
http://www.boost.org/doc/libs/1_54_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html
<http://www.boost.org/doc/libs/1_54_0/libs/geometry/doc/html/geometry/spatial_indexes/introduction.html>  

Results_-_linear_16,_bulk.pdf
<http://boost-geometry.203548.n3.nabble.com/file/n4025741/Results_-_linear_16%2C_bulk.pdf>  
Results_-_linear_16.pdf
<http://boost-geometry.203548.n3.nabble.com/file/n4025741/Results_-_linear_16.pdf>  

--
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-tp4025741.html
Sent from the Boost Geometry mailing list archive at Nabble.com.