libs/geometry/doc/html/geometry/spatial_indexes/introduction.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Introduction</title>
   5 <link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
   7 <link rel="home" href="../../index.html" title="Chapter&#160;1.&#160;Geometry">
   8 <link rel="up" href="../spatial_indexes.html" title="Spatial Indexes">
   9 <link rel="prev" href="../spatial_indexes.html" title="Spatial Indexes">
  10 <link rel="next" href="rtree_quickstart.html" title="Quick Start">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="../spatial_indexes.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../spatial_indexes.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rtree_quickstart.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h3 class="title">
  27 <a name="geometry.spatial_indexes.introduction"></a><a class="link" href="introduction.html" title="Introduction">Introduction</a>
  28 </h3></div></div></div>
  29 <p>
  30         The Boost.Geometry.Index is intended to gather data structures called spatial
  31         indexes which may be used to accelerate searching for objects in space. In
  32         general, spatial indexes stores geometric objects' representations and allows
  33         searching for objects occupying some space or close to some point in space.
  34       </p>
  35 <p>
  36         Currently, only one spatial index is implemented - R-tree.
  37       </p>
  38 <h5>
  39 <a name="geometry.spatial_indexes.introduction.h0"></a>
  40         <span class="phrase"><a name="geometry.spatial_indexes.introduction.r_tree"></a></span><a class="link" href="introduction.html#geometry.spatial_indexes.introduction.r_tree">R-tree</a>
  41       </h5>
  42 <p>
  43         R-tree is a tree data structure used for spatial searching. It was proposed
  44         by Antonin Guttman in 1984 <a href="#ftn.geometry.spatial_indexes.introduction.f0" class="footnote" name="geometry.spatial_indexes.introduction.f0"><sup class="footnote">[1]</sup></a> as an expansion of B-tree for multi-dimensional data. It may
  45         be used to store points or volumetric data in order to perform a spatial
  46         query. This query may for example return objects that are inside some area
  47         or are close to some point in space <a href="#ftn.geometry.spatial_indexes.introduction.f1" class="footnote" name="geometry.spatial_indexes.introduction.f1"><sup class="footnote">[2]</sup></a>. It's possible to insert new objects or to remove the ones already
  48         stored.
  49       </p>
  50 <p>
  51         The R-tree structure is presented on the image below. Each R-tree's node
  52         store a box describing the space occupied by its children nodes. At the bottom
  53         of the structure, there are leaf-nodes which contains values (geometric objects
  54         representations).
  55       </p>
  56 <p>
  57         <span class="inlinemediaobject"><img src="../../img/index/rtree/rstar.png" alt="rstar"></span>
  58       </p>
  59 <p>
  60         The R-tree is a self-balanced data structure. The key part of balancing algorithm
  61         is node splitting algorithm <a href="#ftn.geometry.spatial_indexes.introduction.f2" class="footnote" name="geometry.spatial_indexes.introduction.f2"><sup class="footnote">[3]</sup></a> <a href="#ftn.geometry.spatial_indexes.introduction.f3" class="footnote" name="geometry.spatial_indexes.introduction.f3"><sup class="footnote">[4]</sup></a>. Each algorithm produces different splits so the internal structure
  62         of a tree may be different for each one of them. In general, more complex
  63         algorithms analyses elements better and produces less overlapping nodes.
  64         In the searching process less nodes must be traversed in order to find desired
  65         objects. On the other hand more complex analysis takes more time. In general
  66         faster inserting will result in slower searching and vice versa. The performance
  67         of the R-tree depends on balancing algorithm, parameters and data inserted
  68         into the container.
  69       </p>
  70 <p>
  71         Additionally there are also algorithms creating R-tree containing some, number
  72         of objects. This technique is called bulk loading and is done by use of packing
  73         algorithm <a href="#ftn.geometry.spatial_indexes.introduction.f4" class="footnote" name="geometry.spatial_indexes.introduction.f4"><sup class="footnote">[5]</sup></a> <a href="#ftn.geometry.spatial_indexes.introduction.f5" class="footnote" name="geometry.spatial_indexes.introduction.f5"><sup class="footnote">[6]</sup></a>. This method is faster and results in R-trees with better internal
  74         structure. This means that the query performance is increased.
  75       </p>
  76 <p>
  77         The examples of structures of trees created by use of different algorithms
  78         and exemplary operations times are presented below.
  79       </p>
  80 <div class="informaltable"><table class="table">
  81 <colgroup>
  82 <col>
  83 <col>
  84 <col>
  85 <col>
  86 <col>
  87 </colgroup>
  88 <thead><tr>
  89 <th>
  90               </th>
  91 <th>
  92                 <p>
  93                   Linear algorithm
  94                 </p>
  95               </th>
  96 <th>
  97                 <p>
  98                   Quadratic algorithm
  99                 </p>
 100               </th>
 101 <th>
 102                 <p>
 103                   R*-tree
 104                 </p>
 105               </th>
 106 <th>
 107                 <p>
 108                   Packing algorithm
 109                 </p>
 110               </th>
 111 </tr></thead>
 112 <tbody>
 113 <tr>
 114 <td>
 115                 <p>
 116                   <span class="bold"><strong>Example structure</strong></span>
 117                 </p>
 118               </td>
 119 <td>
 120                 <p>
 121                   <span class="inlinemediaobject"><img src="../../img/index/rtree/linear.png" alt="linear"></span>
 122                 </p>
 123               </td>
 124 <td>
 125                 <p>
 126                   <span class="inlinemediaobject"><img src="../../img/index/rtree/quadratic.png" alt="quadratic"></span>
 127                 </p>
 128               </td>
 129 <td>
 130                 <p>
 131                   <span class="inlinemediaobject"><img src="../../img/index/rtree/rstar.png" alt="rstar"></span>
 132                 </p>
 133               </td>
 134 <td>
 135                 <p>
 136                   <span class="inlinemediaobject"><img src="../../img/index/rtree/bulk.png" alt="bulk"></span>
 137                 </p>
 138               </td>
 139 </tr>
 140 <tr>
 141 <td>
 142                 <p>
 143                   <span class="bold"><strong>1M Values inserts</strong></span>
 144                 </p>
 145               </td>
 146 <td>
 147                 <p>
 148                   1.76s
 149                 </p>
 150               </td>
 151 <td>
 152                 <p>
 153                   2.47s
 154                 </p>
 155               </td>
 156 <td>
 157                 <p>
 158                   6.19s
 159                 </p>
 160               </td>
 161 <td>
 162                 <p>
 163                   0.64s
 164                 </p>
 165               </td>
 166 </tr>
 167 <tr>
 168 <td>
 169                 <p>
 170                   <span class="bold"><strong>100k spatial queries</strong></span>
 171                 </p>
 172               </td>
 173 <td>
 174                 <p>
 175                   2.21s
 176                 </p>
 177               </td>
 178 <td>
 179                 <p>
 180                   0.51s
 181                 </p>
 182               </td>
 183 <td>
 184                 <p>
 185                   0.12s
 186                 </p>
 187               </td>
 188 <td>
 189                 <p>
 190                   0.07s
 191                 </p>
 192               </td>
 193 </tr>
 194 <tr>
 195 <td>
 196                 <p>
 197                   <span class="bold"><strong>100k knn queries</strong></span>
 198                 </p>
 199               </td>
 200 <td>
 201                 <p>
 202                   6.37s
 203                 </p>
 204               </td>
 205 <td>
 206                 <p>
 207                   2.09s
 208                 </p>
 209               </td>
 210 <td>
 211                 <p>
 212                   0.64s
 213                 </p>
 214               </td>
 215 <td>
 216                 <p>
 217                   0.52s
 218                 </p>
 219               </td>
 220 </tr>
 221 </tbody>
 222 </table></div>
 223 <p>
 224         The performance of the R-tree for different values of Max parameter and Min=0.5*Max
 225         is presented in the table below. The configuration of the machine used for
 226         testing is: <span class="emphasis"><em>Intel(R) Core(TM) i7 870 @ 2.93GHz, 8GB RAM, MS Windows
 227         7 x64</em></span>. In the two upper figures you can see the performance of
 228         the R-tree storing random, relatively small, non-overlapping, 2d boxes. In
 229         the lower ones, the performance of the R-tree also storing random, 2d boxes,
 230         but this time quite big and possibly overlapping. As you can see, the R-tree
 231         performance is different in both cases.
 232       </p>
 233 <div class="informaltable"><table class="table">
 234 <colgroup>
 235 <col>
 236 <col>
 237 <col>
 238 </colgroup>
 239 <thead><tr>
 240 <th>
 241               </th>
 242 <th>
 243                 <p>
 244                   building
 245                 </p>
 246               </th>
 247 <th>
 248                 <p>
 249                   querying
 250                 </p>
 251               </th>
 252 </tr></thead>
 253 <tbody>
 254 <tr>
 255 <td>
 256                 <p>
 257                   <span class="bold"><strong>non overlapping</strong></span>
 258                 </p>
 259               </td>
 260 <td>
 261                 <p>
 262                   <span class="inlinemediaobject"><img src="../../img/index/rtree/build_non_ovl.png" alt="build_non_ovl"></span>
 263                 </p>
 264               </td>
 265 <td>
 266                 <p>
 267                   <span class="inlinemediaobject"><img src="../../img/index/rtree/query_non_ovl.png" alt="query_non_ovl"></span>
 268                 </p>
 269               </td>
 270 </tr>
 271 <tr>
 272 <td>
 273                 <p>
 274                   <span class="bold"><strong>overlapping</strong></span>
 275                 </p>
 276               </td>
 277 <td>
 278                 <p>
 279                   <span class="inlinemediaobject"><img src="../../img/index/rtree/build_ovl.png" alt="build_ovl"></span>
 280                 </p>
 281               </td>
 282 <td>
 283                 <p>
 284                   <span class="inlinemediaobject"><img src="../../img/index/rtree/query_ovl.png" alt="query_ovl"></span>
 285                 </p>
 286               </td>
 287 </tr>
 288 </tbody>
 289 </table></div>
 290 <h5>
 291 <a name="geometry.spatial_indexes.introduction.h1"></a>
 292         <span class="phrase"><a name="geometry.spatial_indexes.introduction.implementation_details"></a></span><a class="link" href="introduction.html#geometry.spatial_indexes.introduction.implementation_details">Implementation
 293         details</a>
 294       </h5>
 295 <p>
 296         Key features of this implementation of the R-tree are:
 297       </p>
 298 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 299 <li class="listitem">
 300             capable to store arbitrary Value type,
 301           </li>
 302 <li class="listitem">
 303             three different balancing algorithms - linear, quadratic or rstar,
 304           </li>
 305 <li class="listitem">
 306             creation using packing algorithm,
 307           </li>
 308 <li class="listitem">
 309             parameters (including maximal and minimal number of elements) may be
 310             passed as compile- or run-time parameters, in compile-time version nodes
 311             elements are stored in static-size containers,
 312           </li>
 313 <li class="listitem">
 314             advanced queries, e.g. search for 5 nearest Values to some point and
 315             intersecting some Geometry but not within the other one,
 316           </li>
 317 <li class="listitem">
 318             iterative queries by use of iterators,
 319           </li>
 320 <li class="listitem">
 321             C++11 conformant - move semantics, stateful allocators,
 322           </li>
 323 <li class="listitem">
 324             capable to store Value type with no default constructor,
 325           </li>
 326 <li class="listitem">
 327             in-memory storage by use of the default std::allocator&lt;&gt;,
 328           </li>
 329 <li class="listitem">
 330             other storage options - shared memory and mapped file by use of Boost.Interprocess
 331             allocators.
 332           </li>
 333 </ul></div>
 334 <h5>
 335 <a name="geometry.spatial_indexes.introduction.h2"></a>
 336         <span class="phrase"><a name="geometry.spatial_indexes.introduction.dependencies"></a></span><a class="link" href="introduction.html#geometry.spatial_indexes.introduction.dependencies">Dependencies</a>
 337       </h5>
 338 <p>
 339         R-tree depends on Boost.Container, Boost.Core, Boost.Move, Boost.MPL, Boost.Range,
 340         Boost.Tuple.
 341       </p>
 342 <h5>
 343 <a name="geometry.spatial_indexes.introduction.h3"></a>
 344         <span class="phrase"><a name="geometry.spatial_indexes.introduction.contributors"></a></span><a class="link" href="introduction.html#geometry.spatial_indexes.introduction.contributors">Contributors</a>
 345       </h5>
 346 <p>
 347         The spatial index was originally started by Federico J. Fernandez during
 348         the Google Summer of Code 2008 program, mentored by Hartmut Kaiser.
 349       </p>
 350 <h5>
 351 <a name="geometry.spatial_indexes.introduction.h4"></a>
 352         <span class="phrase"><a name="geometry.spatial_indexes.introduction.spatial_thanks"></a></span><a class="link" href="introduction.html#geometry.spatial_indexes.introduction.spatial_thanks">Spatial thanks</a>
 353       </h5>
 354 <p>
 355         I'd like to thank Barend Gehrels, Bruno Lalande, Mateusz &#321;oskot, Lucanus
 356         J. Simonson for their support and ideas.
 357       </p>
 358 <div class="footnotes">
 359 <br><hr style="width:100; text-align:left;margin-left: 0">
 360 <div id="ftn.geometry.spatial_indexes.introduction.f0" class="footnote"><p><a href="#geometry.spatial_indexes.introduction.f0" class="para"><sup class="para">[1] </sup></a>
 361           Guttman, A. (1984). <span class="emphasis"><em>R-Trees: A Dynamic Index Structure for Spatial
 362           Searching</em></span>
 363         </p></div>
 364 <div id="ftn.geometry.spatial_indexes.introduction.f1" class="footnote"><p><a href="#geometry.spatial_indexes.introduction.f1" class="para"><sup class="para">[2] </sup></a>
 365           Cheung, K.; Fu, A. (1998). <span class="emphasis"><em>Enhanced Nearest Neighbour Search
 366           on the R-tree</em></span>
 367         </p></div>
 368 <div id="ftn.geometry.spatial_indexes.introduction.f2" class="footnote"><p><a href="#geometry.spatial_indexes.introduction.f2" class="para"><sup class="para">[3] </sup></a>
 369           Greene, D. (1989). <span class="emphasis"><em>An implementation and performance analysis
 370           of spatial data access methods</em></span>
 371         </p></div>
 372 <div id="ftn.geometry.spatial_indexes.introduction.f3" class="footnote"><p><a href="#geometry.spatial_indexes.introduction.f3" class="para"><sup class="para">[4] </sup></a>
 373           Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). <span class="emphasis"><em>The
 374           R*-tree: an efficient and robust access method for points and rectangles</em></span>
 375         </p></div>
 376 <div id="ftn.geometry.spatial_indexes.introduction.f4" class="footnote"><p><a href="#geometry.spatial_indexes.introduction.f4" class="para"><sup class="para">[5] </sup></a>
 377           Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (1997).
 378           <span class="emphasis"><em>STR: A Simple and Efficient Algorithm for R-Tree Packing</em></span>
 379         </p></div>
 380 <div id="ftn.geometry.spatial_indexes.introduction.f5" class="footnote"><p><a href="#geometry.spatial_indexes.introduction.f5" class="para"><sup class="para">[6] </sup></a>
 381           Garcia, Yvan J.; Lopez, Mario A.; Leutenegger, Scott T. (1997). <span class="emphasis"><em>A
 382           Greedy Algorithm for Bulk Loading R-trees</em></span>
 383         </p></div>
 384 </div>
 385 </div>
 386 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 387 <td align="left"></td>
 388 <td align="right"><div class="copyright-footer">Copyright &#169; 2009-2014 Barend Gehrels, Bruno Lalande, Mateusz Loskot, Adam
 389       Wulkiewicz, Oracle and/or its affiliates<p>
 390         Distributed under the Boost Software License, Version 1.0. (See accompanying
 391         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 392       </p>
 393 </div></td>
 394 </tr></table>
 395 <hr>
 396 <div class="spirit-nav">
 397 <a accesskey="p" href="../spatial_indexes.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../spatial_indexes.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="rtree_quickstart.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
 398 </div>
 399 </body>
 400 </html>