Date: 2008-08-17 22:20:21
Date: 2008-08-17 22:20:21 EDT (Sun, 17 Aug 2008)
New Revision: 48187
- Performance comparison
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/doc/performance_comparison.qbk (contents, props changed)
Text files modified:
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/doc/spatial_index.qbk | 17 +++++++++++++++--
1 files changed, 15 insertions(+), 2 deletions(-)
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/doc/performance_comparison.qbk 2008-08-17 22:20:21 EDT (Sun, 17 Aug 2008)
@@ -0,0 +1,71 @@
+[/ Boost.SpatialIndex - FAQ ]
+[/ Copyright 2008 Federico J. Fernandez ]
+[/ Distributed under the Boost Software License, Version 1.0. (See]
+[/ accompanying file LICENSE_1_0.txt or copy at ]
+[/ http://www.boost.org/LICENSE_1_0.txt) ]
+[/ See http://www.boost.org/ for latest version. ]
+[section:performance_comparison Performance Comparison]
+In order to show the strenghts of each index we have run several tests
+comparing them with the same data sets to check both processor and
+Also we have compared our library with some well-known spatial indexing
+libraries. The results were really good in comparison.
+[subsection:processor_times Data set]
+For every test we used a GIS data set consisting in 220.000 unique points.
+The complete data set was read from disk, and then loaded into each
+index, using individual insertions.
+[subsection:processor_times Processor times]
+The processor benchmarks were done inserting the complete test data
+set, then doing several searches and finally making some remove
+The searches were done in two phases:
+- 100000 individual searches of random positions
+- a big search of an area returning near 96000 elements.
+About the remove operations we have done 10000 of them.
+For the quadtree the insertion phase takes only 3 seconds. And
+one second for the 100000 random searches. The area search
+is retrieved in less than one second.
+Also, as the number of points per node is variable we compared the
+performance for different node sizes, and greater sizes tend to be
+slower at insertion, but not much faster for querying.
+Let's analyze the rtree. In this case we have two
+parameters to analyze, the minimum (m) and maximum (M) number of
+elements per node.
+The best results for the insertion are with (m, M) = (4, 8). It takes
+15 secs. for the insertion and less than 1 second for the
+box query. The 100000 random queries are done in 6 seconds.
+Meanwhile with (m, M) = (64, 32) we get the worst results, with an
+insertion time of 30 seconds and the 100000 around 9
+In conclusion, the performance for insert seems to be slower than
+quadtree because here the structure is more complicated (lots of splits are happening).
+[subsection:processor_times Memory times]
+We measured the memory consumption after the initial data load.
+The data size es 13 MB.
+For the quadtree, the total memory consumption was 27 MB which
+means that the index takes near 14 MB.
+For the rtree, the memory allocation was of approximately 15 MB.
+In conclusion, there isn't a big difference between both trees.
\ No newline at end of file
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/doc/spatial_index.qbk (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/doc/spatial_index.qbk 2008-08-17 22:20:21 EDT (Sun, 17 Aug 2008)
@@ -1,4 +1,3 @@
[library Spatial Index
@@ -29,7 +28,21 @@
+* [link tutorials.tutorial1 Tutorial 1 - Basic usage]
+* [link tutorials.tutorial2 Tutorial 2 - rtree particularities]
+* [link tutorials.tutorial3 Tutorial 3 - Using your own point structure]
+* [link index_types Index Types]
+* [link performance_comparison Performance comparison]
+* [link faq FAQ]
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk