]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/============================================================================ |
2 | Boost.Geometry Index | |
3 | ||
4 | Copyright (c) 2011-2012 Adam Wulkiewicz. | |
5 | ||
6 | Use, modification and distribution is subject to the Boost Software License, | |
7 | Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
8 | http://www.boost.org/LICENSE_1_0.txt) | |
9 | =============================================================================/] | |
10 | ||
11 | [section Introduction] | |
12 | ||
13 | __rtree__ is a tree data structure used for spatial searching. It was proposed by | |
14 | Antonin Guttman in 1984 [footnote Guttman, A. (1984). /R-Trees: A Dynamic Index Structure for Spatial Searching/] | |
15 | as an expansion of B-tree for multi-dimensional data. It may be used to store points or volumetric data in order to | |
16 | perform a spatial query later. This query may return objects that are inside some area or are close to some point in space | |
17 | [footnote Cheung, K.; Fu, A. (1998). /Enhanced Nearest Neighbour Search on the R-tree/]. | |
18 | ||
19 | The __rtree__ structure is presented on the image below. Each __rtree__'s node store a box describing the space occupied by | |
20 | its children nodes. At the bottom of the structure, there are leaf-nodes which contains values | |
21 | (geometric objects representations). | |
22 | ||
23 | [$img/index/rtree/rstar.png] | |
24 | ||
25 | The __rtree__ is a self-balanced data structure. The key part of balancing algorithm is node splitting algorithm | |
26 | [footnote Greene, D. (1989). /An implementation and performance analysis of spatial data access methods/] | |
27 | [footnote Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). /The R*-tree: an efficient and robust access method for points and rectangles/]. | |
28 | Each algorithm produces different splits so the internal structure of a tree may be different for each one of them. | |
29 | In general more complex algorithms analyses elements better and produces less overlapping nodes. In the searching process less nodes must be traversed | |
30 | 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 | |
31 | and vice versa. The performance of the R-tree depends on balancing algorithm, parameters and data inserted into the container. | |
32 | Example structures of trees created by use of three different algorithms and operations time are presented below. Data used in benchmark was random, | |
33 | non-overlapping boxes. | |
34 | ||
35 | [table | |
36 | [[] [linear algorithm] [quadratic algorithm] [R*-tree]] | |
37 | [[*Example structure*] [[$img/index/rtree/linear.png]] [[$img/index/rtree/quadratic.png]] [[$img/index/rtree/rstar.png]]] | |
38 | [[*1M Values inserts*] [1.65s] [2.51s] [4.96s]] | |
39 | [[*100k spatial queries*] [0.87s] [0.25s] [0.09s]] | |
40 | [[*100k knn queries*] [3.25s] [1.41s] [0.51s]] | |
41 | ] | |
42 | ||
43 | [heading Implementation details] | |
44 | ||
45 | Key features of this implementation of the __rtree__ are: | |
46 | ||
47 | * capable to store arbitrary __value__ type, | |
48 | * three different creation algorithms - linear, quadratic or rstar, | |
49 | * parameters (including maximal and minimal number of elements) may be passed as compile- or run-time parameters, | |
50 | * advanced queries - e.g. search for 5 nearest values to some point and intersecting some region but not within the other one, | |
51 | * C++11 conformant: move semantics, stateful allocators, | |
52 | * capable to store __value__ type with no default constructor. | |
53 | ||
54 | [heading Dependencies] | |
55 | ||
56 | R-tree depends on *Boost.Move*, *Boost.Container*, *Boost.Tuple*, *Boost.Utility*, *Boost.MPL*. | |
57 | ||
58 | [heading Contributors] | |
59 | ||
60 | The spatial index was originally started by Federico J. Fernandez during the Google Summer of Code 2008 program, mentored by Hartmut Kaiser. | |
61 | ||
62 | [heading Spatial thanks] | |
63 | ||
64 | I'd like to thank Barend Gehrels, Bruno Lalande, Mateusz Łoskot, Lucanus J. Simonson for their support and ideas. | |
65 | ||
66 | [endsect] | |
67 | ||
68 |