1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.79.1"> 7<link rel="home" href="../../index.html" title="Chapter 1. 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 configuration of the machine used for testing was: <span class="emphasis"><em>Intel(R) 225 Core(TM) i7 870 @ 2.93GHz, 8GB RAM, MS Windows 7 x64</em></span>. The code 226 was compiled with optimization for speed (<code class="computeroutput"><span class="identifier">O2</span></code>). 227 </p> 228<p> 229 The performance of the R-tree for different values of Max parameter and Min=0.5*Max 230 is presented in the table below. In the two upper figures you can see the 231 performance of the R-tree storing random, relatively small, non-overlapping, 232 2d boxes. In the lower ones, the performance of the R-tree also storing random, 233 2d boxes, but this time quite big and possibly overlapping. As you can see, 234 the R-tree performance is different in both cases. 235 </p> 236<div class="informaltable"><table class="table"> 237<colgroup> 238<col> 239<col> 240<col> 241</colgroup> 242<thead><tr> 243<th> 244 </th> 245<th> 246 <p> 247 building 248 </p> 249 </th> 250<th> 251 <p> 252 querying 253 </p> 254 </th> 255</tr></thead> 256<tbody> 257<tr> 258<td> 259 <p> 260 <span class="bold"><strong>non overlapping</strong></span> 261 </p> 262 </td> 263<td> 264 <p> 265 <span class="inlinemediaobject"><img src="../../img/index/rtree/build_non_ovl.png" alt="build_non_ovl"></span> 266 </p> 267 </td> 268<td> 269 <p> 270 <span class="inlinemediaobject"><img src="../../img/index/rtree/query_non_ovl.png" alt="query_non_ovl"></span> 271 </p> 272 </td> 273</tr> 274<tr> 275<td> 276 <p> 277 <span class="bold"><strong>overlapping</strong></span> 278 </p> 279 </td> 280<td> 281 <p> 282 <span class="inlinemediaobject"><img src="../../img/index/rtree/build_ovl.png" alt="build_ovl"></span> 283 </p> 284 </td> 285<td> 286 <p> 287 <span class="inlinemediaobject"><img src="../../img/index/rtree/query_ovl.png" alt="query_ovl"></span> 288 </p> 289 </td> 290</tr> 291</tbody> 292</table></div> 293<h5> 294<a name="geometry.spatial_indexes.introduction.h1"></a> 295 <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 296 details</a> 297 </h5> 298<p> 299 Key features of this implementation of the R-tree are: 300 </p> 301<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 302<li class="listitem"> 303 capable to store arbitrary Value type, 304 </li> 305<li class="listitem"> 306 three different balancing algorithms - linear, quadratic or rstar, 307 </li> 308<li class="listitem"> 309 creation using packing algorithm, 310 </li> 311<li class="listitem"> 312 parameters (including maximal and minimal number of elements) may be 313 passed as compile- or run-time parameters, in compile-time version nodes 314 elements are stored in static-size containers, 315 </li> 316<li class="listitem"> 317 advanced queries, e.g. search for 5 nearest Values to some point and 318 intersecting some Geometry but not within the other one, 319 </li> 320<li class="listitem"> 321 iterative queries by use of iterators, 322 </li> 323<li class="listitem"> 324 C++11 conformant - move semantics, stateful allocators, 325 </li> 326<li class="listitem"> 327 capable to store Value type with no default constructor, 328 </li> 329<li class="listitem"> 330 in-memory storage by use of the default std::allocator<>, 331 </li> 332<li class="listitem"> 333 other storage options - shared memory and mapped file by use of Boost.Interprocess 334 allocators. 335 </li> 336</ul></div> 337<h5> 338<a name="geometry.spatial_indexes.introduction.h2"></a> 339 <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> 340 </h5> 341<p> 342 R-tree depends on Boost.Container, Boost.Core, Boost.Move, Boost.MPL, Boost.Range, 343 Boost.Tuple. 344 </p> 345<h5> 346<a name="geometry.spatial_indexes.introduction.h3"></a> 347 <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> 348 </h5> 349<p> 350 The spatial index was originally started by Federico J. Fernandez during 351 the Google Summer of Code 2008 program, mentored by Hartmut Kaiser. 352 </p> 353<h5> 354<a name="geometry.spatial_indexes.introduction.h4"></a> 355 <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> 356 </h5> 357<p> 358 I'd like to thank Barend Gehrels, Bruno Lalande, Mateusz Łoskot, Lucanus 359 J. Simonson for their support and ideas. 360 </p> 361<div class="footnotes"> 362<br><hr style="width:100; text-align:left;margin-left: 0"> 363<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> 364 Guttman, A. (1984). <span class="emphasis"><em>R-Trees: A Dynamic Index Structure for Spatial 365 Searching</em></span> 366 </p></div> 367<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> 368 Cheung, K.; Fu, A. (1998). <span class="emphasis"><em>Enhanced Nearest Neighbour Search 369 on the R-tree</em></span> 370 </p></div> 371<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> 372 Greene, D. (1989). <span class="emphasis"><em>An implementation and performance analysis 373 of spatial data access methods</em></span> 374 </p></div> 375<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> 376 Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). <span class="emphasis"><em>The 377 R*-tree: an efficient and robust access method for points and rectangles</em></span> 378 </p></div> 379<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> 380 Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (1997). 381 <span class="emphasis"><em>STR: A Simple and Efficient Algorithm for R-Tree Packing</em></span> 382 </p></div> 383<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> 384 Garcia, Yvan J.; Lopez, Mario A.; Leutenegger, Scott T. (1997). <span class="emphasis"><em>A 385 Greedy Algorithm for Bulk Loading R-trees</em></span> 386 </p></div> 387</div> 388</div> 389<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 390<td align="left"></td> 391<td align="right"><div class="copyright-footer">Copyright © 2009-2019 Barend Gehrels, Bruno Lalande, Mateusz Loskot, Adam 392 Wulkiewicz, Oracle and/or its affiliates<p> 393 Distributed under the Boost Software License, Version 1.0. (See accompanying 394 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>) 395 </p> 396</div></td> 397</tr></table> 398<hr> 399<div class="spirit-nav"> 400<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> 401</div> 402</body> 403</html> 404
