|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r82896 - in sandbox-branches/geometry/index/doc: html html/geometry_index/r_tree rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2013-02-14 21:56:27
Author: awulkiew
Date: 2013-02-14 21:56:24 EST (Thu, 14 Feb 2013)
New Revision: 82896
URL: http://svn.boost.org/trac/boost/changeset/82896
Log:
Rtree introduction improved
Text files modified:
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html | 30 ++++++++++++++++--------------
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/reference.html | 18 +++++++++---------
sandbox-branches/geometry/index/doc/html/index.html | 2 +-
sandbox-branches/geometry/index/doc/rtree/introduction.qbk | 14 ++++++++------
4 files changed, 34 insertions(+), 30 deletions(-)
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/introduction.html 2013-02-14 21:56:24 EST (Thu, 14 Feb 2013)
@@ -56,9 +56,11 @@
algorithms analyses elements better and produces less overlapping nodes.
In the searching process less nodes must be traversed in order to find desired
obejcts. On the other hand more complex analysis takes more time. In general
- faster inserting will result in slower searching and vice versa. Example
- structures of trees created by use of three different algorithms and operations
- time are presented below.
+ faster inserting will result in slower searching and vice versa. The performance
+ of the R-tree depends on balancing algorithm, parameters and data inserted
+ into the container. Example structures of trees created by use of three different
+ algorithms and operations time are presented below. Data used in benchmark
+ was random, non-overlapping boxes.
</p>
<div class="informaltable"><table class="table">
<colgroup>
@@ -90,7 +92,7 @@
<tr>
<td>
<p>
- <span class="bold"><strong>Structure</strong></span>
+ <span class="bold"><strong>Example structure</strong></span>
</p>
</td>
<td>
@@ -117,39 +119,39 @@
</td>
<td>
<p>
- 1.85s
+ 2.11s
</p>
</td>
<td>
<p>
- 3.10s
+ 2.98s
</p>
</td>
<td>
<p>
- 24.52s
+ 5.49s
</p>
</td>
</tr>
<tr>
<td>
<p>
- <span class="bold"><strong>1M spatial queries</strong></span>
+ <span class="bold"><strong>100k spatial queries</strong></span>
</p>
</td>
<td>
<p>
- 8.60s
+ 1.52s
</p>
</td>
<td>
<p>
- 2.74s
+ 0.45s
</p>
</td>
<td>
<p>
- 1.31s
+ 0.17s
</p>
</td>
</tr>
@@ -161,17 +163,17 @@
</td>
<td>
<p>
- 3.49s
+ 4.51s
</p>
</td>
<td>
<p>
- 1.59s
+ 2.22s
</p>
</td>
<td>
<p>
- 0.84s
+ 0.6s
</p>
</td>
</tr>
Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/reference.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/reference.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/reference.html 2013-02-14 21:56:24 EST (Thu, 14 Feb 2013)
@@ -47,7 +47,7 @@
<a name="geometry_index.r_tree.reference.boost_geometry_index_rtree"></a><a name="classboost_1_1geometry_1_1index_1_1rtree"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.boost_geometry_index_rtree" title="boost::geometry::index::rtree">boost::geometry::index::rtree</a>
</h4></div></div></div>
<p>
- <a class="indexterm" name="idp10109888"></a><a class="indexterm" name="idp10110232"></a><a class="indexterm" name="idp10110576"></a><a class="indexterm" name="idp10110920"></a>
+ <a class="indexterm" name="idp10092064"></a><a class="indexterm" name="idp10092408"></a><a class="indexterm" name="idp10092752"></a><a class="indexterm" name="idp10093096"></a>
The R-tree spatial index.
</p>
<h6>
@@ -4500,7 +4500,7 @@
<a name="geometry_index.r_tree.reference.parameters.boost_geometry_index_linear"></a><a name="structboost_1_1geometry_1_1index_1_1linear"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.parameters.boost_geometry_index_linear" title="boost::geometry::index::linear">boost::geometry::index::linear</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp11524632"></a><a class="indexterm" name="idp11524960"></a><a class="indexterm" name="idp11525304"></a><a class="indexterm" name="idp11525648"></a>
+ <a class="indexterm" name="idp11507152"></a><a class="indexterm" name="idp11507480"></a><a class="indexterm" name="idp11507824"></a><a class="indexterm" name="idp11508168"></a>
Linear r-tree creation algorithm parameters.
</p>
<h6>
@@ -4575,7 +4575,7 @@
<a name="geometry_index.r_tree.reference.parameters.boost_geometry_index_quadratic"></a><a name="structboost_1_1geometry_1_1index_1_1quadratic"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.parameters.boost_geometry_index_quadratic" title="boost::geometry::index::quadratic">boost::geometry::index::quadratic</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp11549456"></a><a class="indexterm" name="idp11549784"></a><a class="indexterm" name="idp11550128"></a><a class="indexterm" name="idp11550472"></a>
+ <a class="indexterm" name="idp11532072"></a><a class="indexterm" name="idp11532400"></a><a class="indexterm" name="idp11532744"></a><a class="indexterm" name="idp11533088"></a>
Quadratic r-tree creation algorithm parameters.
</p>
<h6>
@@ -4650,7 +4650,7 @@
<a name="geometry_index.r_tree.reference.parameters.boost_geometry_index_rstar"></a><a name="structboost_1_1geometry_1_1index_1_1rstar"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.parameters.boost_geometry_index_rstar" title="boost::geometry::index::rstar">boost::geometry::index::rstar</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp11574400"></a><a class="indexterm" name="idp11574728"></a><a class="indexterm" name="idp11575072"></a><a class="indexterm" name="idp11575416"></a>
+ <a class="indexterm" name="idp11557040"></a><a class="indexterm" name="idp11557368"></a><a class="indexterm" name="idp11557712"></a><a class="indexterm" name="idp11558056"></a>
R*-tree creation algorithm parameters.
</p>
<h6>
@@ -4754,7 +4754,7 @@
<a name="geometry_index.r_tree.reference.parameters.boost_geometry_index_runtime_linear"></a><a name="classboost_1_1geometry_1_1index_1_1runtime_1_1linear"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.parameters.boost_geometry_index_runtime_linear" title="boost::geometry::index::runtime::linear">boost::geometry::index::runtime::linear</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp11609120"></a><a class="indexterm" name="idp11609448"></a><a class="indexterm" name="idp11609792"></a><a class="indexterm" name="idp11610136"></a><a class="indexterm" name="idp11610480"></a>
+ <a class="indexterm" name="idp11591600"></a><a class="indexterm" name="idp11591928"></a><a class="indexterm" name="idp11592272"></a><a class="indexterm" name="idp11592616"></a><a class="indexterm" name="idp11592960"></a>
Linear r-tree creation algorithm parameters.
</p>
<h6>
@@ -4890,7 +4890,7 @@
<a name="geometry_index.r_tree.reference.parameters.boost_geometry_index_runtime_quadratic"></a><a name="classboost_1_1geometry_1_1index_1_1runtime_1_1quadratic"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.parameters.boost_geometry_index_runtime_quadratic" title="boost::geometry::index::runtime::quadratic">boost::geometry::index::runtime::quadratic</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp11649080"></a><a class="indexterm" name="idp11649408"></a><a class="indexterm" name="idp11649752"></a><a class="indexterm" name="idp11650096"></a><a class="indexterm" name="idp11650440"></a>
+ <a class="indexterm" name="idp11631496"></a><a class="indexterm" name="idp11631824"></a><a class="indexterm" name="idp11632168"></a><a class="indexterm" name="idp11632512"></a><a class="indexterm" name="idp11632856"></a>
Quadratic r-tree creation algorithm parameters.
</p>
<h6>
@@ -5026,7 +5026,7 @@
<a name="geometry_index.r_tree.reference.parameters.boost_geometry_index_runtime_rstar"></a><a name="classboost_1_1geometry_1_1index_1_1runtime_1_1rstar"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.parameters.boost_geometry_index_runtime_rstar" title="boost::geometry::index::runtime::rstar">boost::geometry::index::runtime::rstar</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp11689232"></a><a class="indexterm" name="idp11689560"></a><a class="indexterm" name="idp11689904"></a><a class="indexterm" name="idp11690248"></a><a class="indexterm" name="idp11690592"></a>
+ <a class="indexterm" name="idp11671568"></a><a class="indexterm" name="idp11671896"></a><a class="indexterm" name="idp11672240"></a><a class="indexterm" name="idp11672584"></a><a class="indexterm" name="idp11672928"></a>
R*-tree creation algorithm parameters.
</p>
<h6>
@@ -6606,7 +6606,7 @@
<a name="geometry_index.r_tree.reference.translators.boost_geometry_index_translator_def"></a><a name="structboost_1_1geometry_1_1index_1_1translator_1_1def"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.translators.boost_geometry_index_translator_def" title="boost::geometry::index::translator::def">boost::geometry::index::translator::def</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp12148744"></a><a class="indexterm" name="idp12149072"></a><a class="indexterm" name="idp12149416"></a><a class="indexterm" name="idp12149760"></a><a class="indexterm" name="idp12150104"></a>
+ <a class="indexterm" name="idp12131160"></a><a class="indexterm" name="idp12131488"></a><a class="indexterm" name="idp12131832"></a><a class="indexterm" name="idp12132176"></a><a class="indexterm" name="idp12132520"></a>
The default translator.
</p>
<h6>
@@ -6676,7 +6676,7 @@
<a name="geometry_index.r_tree.reference.translators.boost_geometry_index_translator_index"></a><a name="classboost_1_1geometry_1_1index_1_1translator_1_1index"></a><a class="link" href="reference.html#geometry_index.r_tree.reference.translators.boost_geometry_index_translator_index" title="boost::geometry::index::translator::index">boost::geometry::index::translator::index</a>
</h5></div></div></div>
<p>
- <a class="indexterm" name="idp12173456"></a><a class="indexterm" name="idp12173784"></a><a class="indexterm" name="idp12174128"></a><a class="indexterm" name="idp12174472"></a><a class="indexterm" name="idp12174816"></a>
+ <a class="indexterm" name="idp12155904"></a><a class="indexterm" name="idp12156232"></a><a class="indexterm" name="idp12156576"></a><a class="indexterm" name="idp12156920"></a><a class="indexterm" name="idp12157264"></a>
The index translator.
</p>
<h6>
Modified: sandbox-branches/geometry/index/doc/html/index.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/index.html (original)
+++ sandbox-branches/geometry/index/doc/html/index.html 2013-02-14 21:56:24 EST (Thu, 14 Feb 2013)
@@ -51,7 +51,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"><p><small>Last revised: February 14, 2013 at 22:35:32 GMT</small></p></td>
+<td align="left"><p><small>Last revised: February 15, 2013 at 02:55:42 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
Modified: sandbox-branches/geometry/index/doc/rtree/introduction.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/introduction.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/introduction.qbk 2013-02-14 21:56:24 EST (Thu, 14 Feb 2013)
@@ -32,14 +32,16 @@
Each algorithm produces different splits so the internal structure of a tree may be different for each one of them.
In general more complex algorithms analyses elements better and produces less overlapping nodes. In the searching process less nodes must be traversed
in order to find desired obejcts. On the other hand more complex analysis takes more time. In general faster inserting will result in slower searching
-and vice versa. Example structures of trees created by use of three different algorithms and operations time are presented below.
+and vice versa. The performance of the R-tree depends on balancing algorithm, parameters and data inserted into the container.
+Example structures of trees created by use of three different algorithms and operations time are presented below. Data used in benchmark was random,
+non-overlapping boxes.
[table
-[[] [linear algorithm] [quadratic algorithm] [R*-tree]]
-[[*Structure*][[$../images/linear.png]] [[$../images/quadratic.png]] [[$../images/rstar.png]]]
-[[*1M Values inserts*] [1.85s] [3.10s] [24.52s]]
-[[*1M spatial queries*][8.60s] [2.74s] [1.31s]]
-[[*100k knn queries*] [3.49s] [1.59s] [0.84s]]
+[[] [linear algorithm] [quadratic algorithm] [R*-tree]]
+[[*Example structure*] [[$../images/linear.png]] [[$../images/quadratic.png]] [[$../images/rstar.png]]]
+[[*1M Values inserts*] [2.11s] [2.98s] [5.49s]]
+[[*100k spatial queries*] [1.52s] [0.45s] [0.17s]]
+[[*100k knn queries*] [4.51s] [2.22s] [0.6s]]
]
[heading Implementation details]
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