|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r84753 - in trunk/libs/geometry/doc: html html/img/index/rtree index
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-12 19:33:59
Author: awulkiew
Date: 2013-06-12 19:33:59 EDT (Wed, 12 Jun 2013)
New Revision: 84753
URL: http://svn.boost.org/trac/boost/changeset/84753
Log:
[geometry][index] docs: Improved introduction, added image of tree created using packing algorithm and plots t(Max) t(Min).
Added:
trunk/libs/geometry/doc/html/img/index/rtree/build_max.png (contents, props changed)
trunk/libs/geometry/doc/html/img/index/rtree/build_min.png (contents, props changed)
trunk/libs/geometry/doc/html/img/index/rtree/bulk.png (contents, props changed)
trunk/libs/geometry/doc/html/img/index/rtree/query_max.png (contents, props changed)
trunk/libs/geometry/doc/html/img/index/rtree/query_min.png (contents, props changed)
Text files modified:
trunk/libs/geometry/doc/html/index.html | 7 +++++--
trunk/libs/geometry/doc/index/introduction.qbk | 36 ++++++++++++++++++++++++++----------
2 files changed, 31 insertions(+), 12 deletions(-)
Added: trunk/libs/geometry/doc/html/img/index/rtree/build_max.png
==============================================================================
Binary file. No diff available.
Added: trunk/libs/geometry/doc/html/img/index/rtree/build_min.png
==============================================================================
Binary file. No diff available.
Added: trunk/libs/geometry/doc/html/img/index/rtree/bulk.png
==============================================================================
Binary file. No diff available.
Added: trunk/libs/geometry/doc/html/img/index/rtree/query_max.png
==============================================================================
Binary file. No diff available.
Added: trunk/libs/geometry/doc/html/img/index/rtree/query_min.png
==============================================================================
Binary file. No diff available.
Modified: trunk/libs/geometry/doc/html/index.html
==============================================================================
--- trunk/libs/geometry/doc/html/index.html Wed Jun 12 19:23:08 2013 (r84752)
+++ trunk/libs/geometry/doc/html/index.html 2013-06-12 19:33:59 EDT (Wed, 12 Jun 2013) (r84753)
@@ -109,18 +109,21 @@
Alfredo Correa (adaption of Boost.Array)
</li>
<li class="listitem">
+ Andrew Hundt (varray container, aka. static_vector)
+ </li>
+<li class="listitem">
Federico Fernández (preliminary version of R-tree spatial index)
</li>
<li class="listitem">
Karsten Ahnert (patch for cross-track distance)
</li>
<li class="listitem">
- Andrew Hundt (varray container, aka. static_vector)
+ Mats Taraldsvik (documentation: adapting a legacy model)
</li>
</ul></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: June 07, 2013 at 20:06:01 GMT</small></p></td>
+<td align="left"><p><small>Last revised: June 12, 2013 at 23:27:34 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
Modified: trunk/libs/geometry/doc/index/introduction.qbk
==============================================================================
--- trunk/libs/geometry/doc/index/introduction.qbk Wed Jun 12 19:23:08 2013 (r84752)
+++ trunk/libs/geometry/doc/index/introduction.qbk 2013-06-12 19:33:59 EDT (Wed, 12 Jun 2013) (r84753)
@@ -23,8 +23,8 @@
Antonin Guttman in 1984 [footnote Guttman, A. (1984). /R-Trees: A Dynamic Index Structure for Spatial Searching/]
as an expansion of B-tree for multi-dimensional data. It may be used to store points or volumetric data in order to
perform a spatial query. This query may for example return objects that are inside some area or are close to some point in space
-[footnote Cheung, K.; Fu, A. (1998). /Enhanced Nearest Neighbour Search on the R-tree/]. It's possible to insert new objects or
-to remove the ones already stored.
+[footnote Cheung, K.; Fu, A. (1998). /Enhanced Nearest Neighbour Search on the R-tree/].
+It's possible to insert new objects or to remove the ones already stored.
The __rtree__ structure is presented on the image below. Each __rtree__'s node store a box describing the space occupied by
its children nodes. At the bottom of the structure, there are leaf-nodes which contains values
@@ -36,18 +36,34 @@
[footnote Greene, D. (1989). /An implementation and performance analysis of spatial data access methods/]
[footnote Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). /The R*-tree: an efficient and robust access method for points and rectangles/].
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 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 objects. On the other hand more complex analysis takes more time. In general 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.
+
+Additionally there are also algorithms creating R-tree containing some, possibly big, number of objects. This technique is called bulk loading and is
+done by use of packing algorithm
+[footnote Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (1997). /STR: A Simple and Efficient Algorithm for R-Tree Packing/]
+[footnote Garcia, Yvan J.; Lopez, Mario A.; Leutenegger, Scott T. (1997). /A Greedy Algorithm for Bulk Loading R-trees/].
+This method is faster and results in R-trees with better internal structure. This means that the query performance is increased.
+
+The examples of structures of trees created by use of different algorithms and exemplary operations times are presented below.
+Data used in benchmark was random 2-dimensional boxes. Trees was created for Max=16, Min=8.
+
+[table
+[[] [Linear algorithm] [Quadratic algorithm] [R*-tree] [Packing algorithm]]
+[[*Example structure*] [[$img/index/rtree/linear.png]] [[$img/index/rtree/quadratic.png]] [[$img/index/rtree/rstar.png]] [[$img/index/rtree/bulk.png]]]
+[[*1M Values inserts*] [1.76s] [2.47s] [8.39s] [1.67s]]
+[[*100k spatial queries*] [2.21] [0.51s] [0.12s] [0.07s]]
+[[*100k knn queries*] [3.25s] [1.41s] [0.51s] [?]]
+]
+
+The performance of the R-tree for different values of Max and Min parameters is presented in the table below.
+The configuration of the machine used for testing is: /Intel(R) Core(TM) i7 870 @ 2.93GHz, 8GB RAM, MS Windows 7 x64/.
[table
-[[] [linear algorithm] [quadratic algorithm] [R*-tree]]
-[[*Example structure*] [[$img/index/rtree/linear.png]] [[$img/index/rtree/quadratic.png]] [[$img/index/rtree/rstar.png]]]
-[[*1M Values inserts*] [1.65s] [2.51s] [4.96s]]
-[[*100k spatial queries*] [0.87s] [0.25s] [0.09s]]
-[[*100k knn queries*] [3.25s] [1.41s] [0.51s]]
+[[] [building] [querying]]
+[[*t(Max)*] [[$img/index/rtree/build_max.png]] [[$img/index/rtree/query_max.png]]]
+[[*t(Min)*] [[$img/index/rtree/build_min.png]] [[$img/index/rtree/query_min.png]]]
]
[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