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