-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathoverview.html
483 lines (476 loc) · 24.3 KB
/
overview.html
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
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Library Overview — libspatialindex 1.9.3 documentation</title>
<link rel="stylesheet" href="_static/nature.css" type="text/css" />
<link rel="stylesheet" href="_static/pygments.css" type="text/css" />
<script id="documentation_options" data-url_root="./" src="_static/documentation_options.js"></script>
<script src="_static/jquery.js"></script>
<script src="_static/underscore.js"></script>
<script src="_static/doctools.js"></script>
<script src="_static/language_data.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="prev" title="Mailing List" href="community.html" />
</head><body>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="community.html" title="Mailing List"
accesskey="P">previous</a> |</li>
<li class="nav-item nav-item-0"><a href="index.html">libspatialindex 1.9.3 documentation</a> »</li>
<li class="nav-item nav-item-this"><a href="">Library Overview</a></li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<div class="section" id="library-overview">
<span id="overview"></span><h1>Library Overview<a class="headerlink" href="#library-overview" title="Permalink to this headline">¶</a></h1>
<dl class="simple">
<dt>The library currently consists of six packages:</dt><dd><ol class="arabic simple">
<li><p>The core spatialindex utilities.</p></li>
<li><p>The storagemanager files.</p></li>
<li><p>The spatialindex interfaces.</p></li>
<li><p>The rtree index.</p></li>
<li><p>The mvrtree index.</p></li>
<li><p>The tprtree index.</p></li>
</ol>
</dd>
</dl>
<p>I will briefly present the basic features supported by each package.
For more details you will have to refer to the code, for now.</p>
<div class="section" id="spatial-index-utilities">
<h2>Spatial Index Utilities<a class="headerlink" href="#spatial-index-utilities" title="Permalink to this headline">¶</a></h2>
<p>To provide common constructors and uniform initialization for all objects
provided by the library a PropertySet class is provided. A PropertySet
associates strings with Variants. Each property corresponds to one string.</p>
<p>A basic implementation of a Variant is also provided that supports a
number of data types. The supported data types can be found in SpatialIndex.h</p>
<p>PropertySet supports three functions:</p>
<blockquote>
<div><ol class="arabic simple">
<li><p>getProperty returns the Variant associated with the given string.</p></li>
<li><p>setProperty associates the given Variant with the given string.</p></li>
<li><p>removeProperty removes the specified property from the PropertySet.</p></li>
</ol>
</div></blockquote>
<p>A number of exceptions are also defined here. All exceptions extend
Exception and thus provide the what() method that returns a string
representation of the exception with useful comments. It is advisable to
use enclosing try/catch blocks when using any library objects. Many
constructors throw exceptions when invalid initialization properties are specified.</p>
<p>A general IShape interface is defined. All shape classes should extend
IShape. Basic Region and Point classes are already provided. Please
check Region.h and Point.h for further details.</p>
</div>
<div class="section" id="storage-manager">
<h2>Storage Manager<a class="headerlink" href="#storage-manager" title="Permalink to this headline">¶</a></h2>
<p>The library provides a common interface for storage management of all
indices. It consists of the IStorageManager interface, which provides functions
for storing and retrieving entities. An entity is viewed as a simple uint8_t
array; hence it can be an index entry, a data entry or anything else that the
user wants to store. The storage manager interface is generic and does not apply
only to spatial indices.</p>
<p>Classes that implement the IStorageManager interface decide on how to
store entities. simple main memory implementation is provided, for example,
that stores the entities using a vector, associating every entity with a
unique ID (the entry’s index in the vector). A disk based storage manager
could choose to store the entities in a simple random access file, or a
database storage manager could store them in a relational table, etc. as long
as unique IDs are associated with every entity. Also, storage managers should
implement their own paging, compaction and deletion policies transparently
from the callers (be it an index or a user).</p>
<p>The storeByteArray method gets a uint8_t array and its length and an entity ID.
If the caller specifies NewPage as the input ID, the storage manager allocates
a new ID, stores the entity and returns the ID associated with the entity.
If, instead, the user specifies an already existing ID the storage manager
overwrites the old data. An exception is thrown if the caller requests
an invalid ID to be overwritten.</p>
<p>The loadByteArray method gets an entity ID and returns the associated uint8_t array
along with its length. If an invalid ID is requested, an exception is thrown.</p>
<p>The deleteByteArray method removes the requested entity from storage.</p>
<p>The storage managers should have no information about the types of entities
that are stored. There are three main reasons for this decision:</p>
<blockquote>
<div><ol class="arabic simple">
<li><p>Any number of spatial indices can be stored in a single storage manager
(i.e. the same relational table, or binary file, or hash table, etc., can
be used to store many indices) using an arbitrary number of pages and
a unique index ID per index (this will be discussed shortly).</p></li>
<li><p>Both clustered and non-clustered indices can be supported. A clustered
index stores the data associated with the entries that it contains along
with the spatial information that it indexes. A non-clustered index stores
only the spatial information of its entries. Any associated data are
stored separately and are associated with the index entries by a unique ID.
To support both types of indices, the storage manager interface should be
quite generic, allowing the index to decide how to store its data.
Otherwise clustered and non-clustered indices would have to be
implemented separately.</p></li>
<li><p>Decision flexibility. For example, the users can choose a clustered index
that will take care of storing everything. They can choose a main memory
non-clustered index and store the actual data in MySQL. They can choose
a disk based non-clustered index and store the data manually in a
separate binary file or even in the same storage manager but doing a low
level customized data processing.</p></li>
</ol>
</div></blockquote>
<p>Two storage managers are provided in the current implementation:</p>
<blockquote>
<div><ol class="arabic simple">
<li><p>MemoryStorageManager</p></li>
<li><p>DiskStorageManager</p></li>
</ol>
</div></blockquote>
<div class="section" id="memorystoragemanager">
<h3>MemoryStorageManager<a class="headerlink" href="#memorystoragemanager" title="Permalink to this headline">¶</a></h3>
<p>As it is implied be the name, this is a main memory implementation. Everything
is stored in main memory using a simple vector. No properties are needed to
initialize a MemoryStorageManager object. When a MemoryStorageManager instance
goes out of scope, all data that it contains are lost.</p>
</div>
<div class="section" id="diskstoragemanager">
<h3>DiskStorageManager<a class="headerlink" href="#diskstoragemanager" title="Permalink to this headline">¶</a></h3>
<p>The disk storage manager uses two random access files for storing information.
One with extension .idx and the other with extension .dat.</p>
<p>A list of all the supported properties that can be provided during
initialization, follows:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 12%" />
<col style="width: 11%" />
<col style="width: 78%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Property</p></th>
<th class="head"><p>Type</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>FileName</p></td>
<td><p>VT_PCHAR</p></td>
<td><p>The base name of the file to open (no extension)</p></td>
</tr>
<tr class="row-odd"><td><p>Overwrite</p></td>
<td><p>VT_BOOL</p></td>
<td><p>If Overwrite is true and a storage manager with the
specified filename already exists, it will be
truncated and overwritten. All data will be lost.</p></td>
</tr>
<tr class="row-even"><td><p>PageSize</p></td>
<td><p>VT_ULONG</p></td>
<td><p>The page size to use. If the specified filename
already exists and Overwrite is false, PageSize is ignored.</p></td>
</tr>
</tbody>
</table>
<p>For entities that are larger than the page size, multiple pages are used.
Although, the empty space on the last page is lost. Also, there is no effort
whatsoever to use as many sequential pages as possible. A future version
might support sequential I/O. Thus, real clustered indices cannot be supported yet.</p>
<p>The purpose of the .idx file is to store vital information like the page size,
the next available page, a list of empty pages and the sequence of pages
associated with every entity ID.</p>
<p>This class also provides a flush method that practically overwrites the
.idx file and syncs both file pointers.</p>
<p>The .idx file is loaded into main memory during initialization and is
written to disk only after flushing the storage manager or during object
destruction. In case of an unexpected failure changes to the storage manager
will be lost due to a stale .idx file. Avoiding such disasters is future work.</p>
</div>
</div>
<div class="section" id="spatialindex-interfaces">
<h2>SpatialIndex Interfaces<a class="headerlink" href="#spatialindex-interfaces" title="Permalink to this headline">¶</a></h2>
<p>A spatial index is any index structure that accesses spatial information
efficiently. It could range from a simple grid file to a complicated tree
structure. A spatial index indexes entries of type IEntry, which can be index
nodes, leaf nodes, data etc. depending on the structure characteristics.
The appropriate interfaces with useful accessor methods should be provided
for all types of entries.</p>
<p>A spatial index should implement the ISpatialIndex interface.</p>
<p>The containmentQuery method requires a query shape and a reference to a
valid IVisitor instance (described shortly). The intersectionQuery method
is the same. Both accept an IShape as the query. If the query shape is a simple
Region, than a classic range query is performed. The user though has the
ability to create her own shapes, thus defining her own intersection and
containment methods making possible to run any kind of range query without
having to modify the index. An example of a trapezoidal query is given in the
regressiontest directory. Have in mind that it is the users responsibility
to implement the correct intersection and containment methods between their
shape and the type of shapes that are stored by the specific index that they
are planning to use. For example, if an rtree index will be used, a trapezoid
should define intersection and containment between itself and Regions, since
all rtree nodes are of type Region. Hence, the user should have some knowledge
about the index internal representation, to run more sophisticated queries.</p>
<p>A point location query is performed using the pointLocationQuery method. It
takes the query point and a visitor as arguments.</p>
<p>Nearest neighbor queries can be performed with the nearestNeighborQuery method.
Its first argument is the number k of nearest neighbors requested. This
method also requires the query shape and a visitor object. The default
implementation uses the getMinimumDistance function of IShape for calculating
the distance of the query from the rectangular node and data entries stored
in the tree. A more sophisticated distance measure can be used by implementing
the INearestNeighborComparator interface and passing it as the last argument
of nearestNeighborQuery. For example, a comparator is necessary when the query
needs to be checked against the actual data stored in the tree, instead of
the rectangular data entry approximations stored in the leaves.</p>
<p>For customizing queries the IVisitor interface (based on the Visitor
pattern [gamma94]) provides callback functions for visiting index and
leaf nodes, as well as data entries. Node and data information can be obtained
using the INode and IData interfaces (both extend IEntry). Examples of using
this interface include visualizing a query, counting the number of leaf
or index nodes visited for a specific query, throwing alerts when a
specific spatial region is accessed, etc.</p>
<p>The queryStrategy method provides the ability to design more sophisticated
queries. It uses the IQueryStrategy interface as a callback that is called
continuously until no more entries are requested. It can be used to
implement custom query algorithms (based on the strategy pattern [gamma94]).</p>
<p>A data entry can be inserted using the insertData method. The insertion
function will convert any shape into an internal representation depending on
the index. Every inserted object should be assigned an ID (called object
identifier) that will allow updating, deleting and reporting the object.
It is the responsibility of the caller to provide the index with IDs
(unique or not). Also, a uint8_t array can be associated with an entry. The
uint8_t arrays are stored along with the spatial information inside the leaf
nodes. Clustered indices can be supported in that way. The uint8_t array can
also by null (in which case the length field should be zero), and no extra
space should be used per node.</p>
<p>A data entry can be deleted using the deleteData method. The object shape
and ID should be provided. Spatial indices cluster objects according to
spatial characteristics and not IDs. Hence, the shape is essential for
locating and deleting an entry.</p>
<p>Useful statistics are provided through the IStatistics interface and
the getStatistics method.</p>
<p>Method getIndexProperties returns a PropertySet with all useful index
properties like dimensionality etc.</p>
<p>A NodeCommand interface is provided for customizing Node operations. Using
the addWriteNodeCommand, addReadNodeCommand and addDeleteNodeCommand methods,
custom command objects are added in listener lists and get executed after
the corresponding operations.</p>
<p>The isIndexValid method performs internal checks for testing the
integrity of a structure. It is used for debugging purposes.</p>
<p>When a new index is created a unique index ID should be assigned to it, that
will be used when reloading the index from persistent storage. This index ID
should be returned as an IndexIdentifier property in the instance of the
PropsertySet that was used for constructing the index instance. Using
index IDs, multiple indices can be stored in the same storage manager.
It is the users responsibility to manager the index IDs. Associating the
wrong index ID with the wrong storage manager or index type has undefined
results.</p>
</div>
<div class="section" id="the-rtree-package">
<h2>The RTree Package<a class="headerlink" href="#the-rtree-package" title="Permalink to this headline">¶</a></h2>
<p>The RTree index [guttman84] is a balanced tree structure that consists of
index nodes, leaf nodes and data. Every node (leaf and index) has a fixed
capacity of entries, (the node capacity) chosen at index creation An RTree
abstracts the data with their Minimum Bounding Region (MBR) and clusters
these MBRs according to various heuristics in the leaf nodes. Queries are
evaluated from the root of the tree down the leaves. Since the index is
balanced nodes can be under full. They cannot be empty though. A fill
factor specifies the minimum number of entries allowed in any node. The
fill factor is usually close to 70%.</p>
<p>RTree creation involves:</p>
<blockquote>
<div><ol class="arabic simple">
<li><p>Deciding if the index will be internal or external memory and selecting
the appropriate storage manager.</p></li>
<li><p>Choosing the index and leaf capacity (also known as fan-out).</p></li>
<li><p>Choosing the fill factor (from 1% to 99% of the node capacity).</p></li>
<li><p>Choosing the dimensionality of the data.</p></li>
<li><p>Choosing the insert/update policy (the RTree variant).</p></li>
</ol>
</div></blockquote>
<p>If an already stored RTree is being reloaded for reuse, only the index ID
needs to be supplied during construction. In that case, some options cannot
be modified. These include: the index and leaf capacity, the fill factor and
the dimensionality. Note here, that the RTree variant can actually be
modified. The variant affects only when and how splitting occurs, and
thus can be changed at any time.</p>
<p>An initialization PropertySet is used for setting the above options,
complying with the following property strings:</p>
<table class="docutils align-default">
<colgroup>
<col style="width: 27%" />
<col style="width: 11%" />
<col style="width: 62%" />
</colgroup>
<thead>
<tr class="row-odd"><th class="head"><p>Property</p></th>
<th class="head"><p>Type</p></th>
<th class="head"><p>Description</p></th>
</tr>
</thead>
<tbody>
<tr class="row-even"><td><p>IndexIndentifier</p></td>
<td><p>VT_LONG</p></td>
<td><p>If specified an existing index will be
opened from the supplied storage manager with
the given index id. Behavior is unspecified
if the index id or the storage manager are incorrect.</p></td>
</tr>
<tr class="row-odd"><td><p>Dimension</p></td>
<td><p>VT_ULONG</p></td>
<td><p>Dimensionality of the data that will be inserted.</p></td>
</tr>
<tr class="row-even"><td><p>IndexCapacity</p></td>
<td><p>VT_ULONG</p></td>
<td><p>The index node capacity. Default is 100.</p></td>
</tr>
<tr class="row-odd"><td><p>LeafCapactiy</p></td>
<td><p>VT_ULONG</p></td>
<td><p>The leaf node capacity. Default is 100.</p></td>
</tr>
<tr class="row-even"><td><p>FillFactor</p></td>
<td><p>VT_DOUBLE</p></td>
<td><p>The fill factor. Default is 70%</p></td>
</tr>
<tr class="row-odd"><td><p>TreeVariant</p></td>
<td><p>VT_LONG</p></td>
<td><p>Can be one of Linear, Quadratic or Rstar. Default is Rstar</p></td>
</tr>
<tr class="row-even"><td><p>NearMinimumOverlapFactor</p></td>
<td><p>VT_ULONG</p></td>
<td><p>Default is 32.</p></td>
</tr>
<tr class="row-odd"><td><p>SplitDistributionFactor</p></td>
<td><p>VT_DOUBLE</p></td>
<td><p>Default is 0.4</p></td>
</tr>
<tr class="row-even"><td><p>ReinsertFactor</p></td>
<td><p>VT_DOUBLE</p></td>
<td><p>Default is 0.3</p></td>
</tr>
<tr class="row-odd"><td><p>EnsureTightMBRs</p></td>
<td><p>VT_BOOL</p></td>
<td><p>Default is true</p></td>
</tr>
<tr class="row-even"><td><p>IndexPoolCapacity</p></td>
<td><p>VT_LONG</p></td>
<td><p>Default is 100</p></td>
</tr>
<tr class="row-odd"><td><p>LeafPoolCapacity</p></td>
<td><p>VT_LONG</p></td>
<td><p>Default is 100</p></td>
</tr>
<tr class="row-even"><td><p>RegionPoolCapacity</p></td>
<td><p>VT_LONG</p></td>
<td><p>Default is 1000</p></td>
</tr>
<tr class="row-odd"><td><p>PointPoolCapacity</p></td>
<td><p>VT_LONG</p></td>
<td><p>Default is 500</p></td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="performance">
<h2>Performance<a class="headerlink" href="#performance" title="Permalink to this headline">¶</a></h2>
<p>Dataset size, data density, etc. have nothing to do with capacity and page
size. What you are trying to achieve is fast reads from the disk and take
advantage of disk buffering and prefetching.</p>
<p>Normally, you select the page size to be equal to the disk page size (depends
on how you format the drive). Then you choose the node capacity to be enough
to fill the whole page (including data entries if you have any).</p>
<p>There is a tradeoff though in making node capacity too large. The larger the
capacity, the longer the “for loops” for inserting, deleting, locating node
entries take (CPU time). On the other hand, the larger the capacity the
shorter the tree becomes, reducing the number of random IOs to reach the
leaves. Hence, you might want to fit multiple nodes (of smaller capacity)
inside a single page to balance I/O and CPU cost, in case your disk page size
is too large.</p>
<p>Finally, if you have enough buffer space to fit most of the index nodes in
main memory, then large capacities do not make too much sense, because the
height of the tree does not matter any more. Of course, the smaller the
capacity, the larger the number of leaf nodes you will have to retrieve from
disk for range queries (point queries and nearest neighbor queries will not
suffer that much). So very small capacities hurt as well.</p>
<p>There is another issue when trying to fit multiple nodes per page: Leftover
space. You might have leftover space due to data entries that do not have a
fixed size. Unfortunately, in that case, leftover space per page is lost,
negatively impacting space usage.</p>
<p>Selecting the right page size is easy; make it equal to the disk page size.
Selecting the right node capacity is an art…</p>
</div>
</div>
<div class="section" id="references">
<h1>References<a class="headerlink" href="#references" title="Permalink to this headline">¶</a></h1>
<dl class="simple">
<dt>[guttman84] “R-Trees: A Dynamic Index Structure for Spatial Searching”</dt><dd><p>Antonin Guttman, Proc. 1984 ACM-SIGMOD Conference on Management of Data (1985), 47-57.</p>
</dd>
<dt>[gamma94] “Design Patterns: Elements of Reusable Object-Oriented Software”</dt><dd><p>Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, Addison Wesley. October 1994.</p>
</dd>
</dl>
</div>
<div class="clearer"></div>
</div>
</div>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">Library Overview</a><ul>
<li><a class="reference internal" href="#spatial-index-utilities">Spatial Index Utilities</a></li>
<li><a class="reference internal" href="#storage-manager">Storage Manager</a><ul>
<li><a class="reference internal" href="#memorystoragemanager">MemoryStorageManager</a></li>
<li><a class="reference internal" href="#diskstoragemanager">DiskStorageManager</a></li>
</ul>
</li>
<li><a class="reference internal" href="#spatialindex-interfaces">SpatialIndex Interfaces</a></li>
<li><a class="reference internal" href="#the-rtree-package">The RTree Package</a></li>
<li><a class="reference internal" href="#performance">Performance</a></li>
</ul>
</li>
<li><a class="reference internal" href="#references">References</a></li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="community.html"
title="previous chapter">Mailing List</a></p>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="_sources/overview.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="search.html" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" />
<input type="submit" value="Go" />
</form>
</div>
</div>
<script>$('#searchbox').show(0);</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related" role="navigation" aria-label="related navigation">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="community.html" title="Mailing List"
>previous</a> |</li>
<li class="nav-item nav-item-0"><a href="index.html">libspatialindex 1.9.3 documentation</a> »</li>
<li class="nav-item nav-item-this"><a href="">Library Overview</a></li>
</ul>
</div>
<div class="footer" role="contentinfo">
© Copyright 2019, Marios Hadjieleftheriou.
Created using <a href="https://www.sphinx-doc.org/">Sphinx</a> 3.1.2.
</div>
</body>
</html>