Geometry Boost List: [ggl] spacial index

Subject: [ggl] spacial index
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-04-27 15:05:34

> Interesting, I'm curious about the result... I was suspecting memory
> consumption problems with the new model, but certainly not performance
> regressions. Probably we'll have to dig to know where they come from
> exactly (hope you have an easy way to switch implementations).

I've eliminated the error by disabling reinsertions for now.

Test programs were compiled using VS2010. For 1000000 boxes with random 
position [-1000000, 1000000] and size 1 and 100000 searches results are 
as follows:

For min:4 max:8
old creation: 8.0s
old search:   3.4s
old size:     47MB
new creation: 6.7s
new search:   7.1s
new size:     49MB

For min:3 max:10
old creation: 8.1s
old search:   1.5s
old size:     43MB
new creation: 9.4s
new search:   5.6s
new size:     66MB

For min:6 max:20
old creation: 7.8s
old search:   1.6s
old size:     37MB
new creation: 21.5s
new search:   38.0s
new size:     46MB

For min:8 max:32
old creation: 8.3s
old search:   1.8s
old size:     31MB
new creation: 48.9s
new search:   132.8s
new size:     44MB

Maby I should implement the same algorithm (linear split?) and then 
perform tests. Or create old rtree, fill the new one with data from the 
old one and then test search speed.

Regards,
Adam