]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/============================================================================ |
2 | Boost.Geometry Index | |
3 | ||
4 | Copyright (c) 2011-2013 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 | The __boost_geometry_index__ is intended to gather data structures called spatial | |
14 | indexes which may be used to accelerate searching for objects in space. In general, | |
15 | spatial indexes stores geometric objects' representations and allows searching for | |
16 | objects occupying some space or close to some point in space. | |
17 | ||
18 | Currently, only one spatial index is implemented - __rtree__. | |
19 | ||
20 | [heading __rtree__] | |
21 | ||
22 | __rtree__ is a tree data structure used for spatial searching. It was proposed by | |
23 | Antonin Guttman in 1984 [footnote Guttman, A. (1984). /R-Trees: A Dynamic Index Structure for Spatial Searching/] | |
24 | as an expansion of B-tree for multi-dimensional data. It may be used to store points or volumetric data in order to | |
25 | perform a spatial query. This query may for example return objects that are inside some area or are close to some point in space | |
26 | [footnote Cheung, K.; Fu, A. (1998). /Enhanced Nearest Neighbour Search on the R-tree/]. | |
27 | It's possible to insert new objects or to remove the ones already stored. | |
28 | ||
29 | The __rtree__ structure is presented on the image below. Each __rtree__'s node store a box describing the space occupied by | |
30 | its children nodes. At the bottom of the structure, there are leaf-nodes which contains values | |
31 | (geometric objects representations). | |
32 | ||
33 | [$img/index/rtree/rstar.png] | |
34 | ||
35 | The __rtree__ is a self-balanced data structure. The key part of balancing algorithm is node splitting algorithm | |
36 | [footnote Greene, D. (1989). /An implementation and performance analysis of spatial data access methods/] | |
37 | [footnote Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). /The R*-tree: an efficient and robust access method for points and rectangles/]. | |
38 | Each algorithm produces different splits so the internal structure of a tree may be different for each one of them. | |
39 | In general, more complex algorithms analyses elements better and produces less overlapping nodes. In the searching process less nodes must be traversed | |
40 | 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 | |
41 | and vice versa. The performance of the R-tree depends on balancing algorithm, parameters and data inserted into the container. | |
42 | ||
43 | Additionally there are also algorithms creating R-tree containing some, number of objects. This technique is called bulk loading and is | |
44 | done by use of packing algorithm | |
45 | [footnote Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (1997). /STR: A Simple and Efficient Algorithm for R-Tree Packing/] | |
46 | [footnote Garcia, Yvan J.; Lopez, Mario A.; Leutenegger, Scott T. (1997). /A Greedy Algorithm for Bulk Loading R-trees/]. | |
47 | This method is faster and results in R-trees with better internal structure. This means that the query performance is increased. | |
48 | ||
49 | The examples of structures of trees created by use of different algorithms and exemplary operations times are presented below. | |
50 | ||
51 | [table | |
52 | [[] [Linear algorithm] [Quadratic algorithm] [R*-tree] [Packing algorithm]] | |
53 | [[*Example structure*] [[$img/index/rtree/linear.png]] [[$img/index/rtree/quadratic.png]] [[$img/index/rtree/rstar.png]] [[$img/index/rtree/bulk.png]]] | |
54 | [[*1M Values inserts*] [1.76s] [2.47s] [6.19s] [0.64s]] | |
55 | [[*100k spatial queries*] [2.21s] [0.51s] [0.12s] [0.07s]] | |
56 | [[*100k knn queries*] [6.37s] [2.09s] [0.64s] [0.52s]] | |
57 | ] | |
58 | ||
59 | The configuration of the machine used for testing was: /Intel(R) Core(TM) i7 870 @ 2.93GHz, 8GB RAM, MS Windows 7 x64/. | |
60 | The code was compiled with optimization for speed (`O2`). | |
61 | ||
62 | The performance of the R-tree for different values of Max parameter and Min=0.5*Max is presented in the table below. | |
63 | In the two upper figures you can see the performance of the __rtree__ storing random, relatively small, non-overlapping, 2d boxes. | |
64 | In the lower ones, the performance of the __rtree__ also storing random, 2d boxes, but this time quite big and possibly overlapping. | |
65 | As you can see, the __rtree__ performance is different in both cases. | |
66 | ||
67 | [table | |
68 | [[] [building] [querying]] | |
69 | [[*non overlapping*] [[$img/index/rtree/build_non_ovl.png]] [[$img/index/rtree/query_non_ovl.png]]] | |
70 | [[*overlapping*] [[$img/index/rtree/build_ovl.png]] [[$img/index/rtree/query_ovl.png]]] | |
71 | ] | |
72 | ||
73 | [heading Implementation details] | |
74 | ||
75 | Key features of this implementation of the __rtree__ are: | |
76 | ||
77 | * capable to store arbitrary __value__ type, | |
78 | * three different balancing algorithms - linear, quadratic or rstar, | |
79 | * creation using packing algorithm, | |
80 | * parameters (including maximal and minimal number of elements) may be passed as compile- or run-time parameters, in compile-time | |
81 | version nodes elements are stored in static-size containers, | |
82 | * advanced queries, e.g. search for 5 nearest Values to some point and intersecting some Geometry but not within the other one, | |
83 | * iterative queries by use of iterators, | |
84 | * C++11 conformant - move semantics, stateful allocators, | |
85 | * capable to store __value__ type with no default constructor, | |
86 | * in-memory storage by use of the default std::allocator<>, | |
87 | * other storage options - shared memory and mapped file by use of Boost.Interprocess allocators. | |
88 | ||
89 | [/ | |
90 | [heading Planned features] | |
91 | ||
92 | Below you can find features that will (or probably will) be added in the future releases: | |
93 | /] | |
94 | [/ Done | |
95 | * rstar optimization (planned for release in Boost 1.55), | |
96 | * bulk loading (planned for release in Boost 1.55), | |
97 | * 'reversed' spatial predicates or additional spatial predicates like contains(), | |
98 | * iterative queries - query iterators / type-erased query iterators, | |
99 | /] | |
100 | [/ | |
101 | * path/ray query predicate - search for Values along Segment or LineString, closest to the starting point, | |
102 | * user-defined distance calculation in nearest() predicate, | |
103 | * serialization, | |
104 | * persistent storage. | |
105 | /] | |
106 | [/ Maybe | |
107 | * other geometries as Indexables, e.g. NSpheres. Rings would probably require using move semantics instead of copying | |
108 | * bounding tree - rtree variation capable to use other Geometries as bounds, e.g. NSpheres, Rings/convex polygons/ (moving required), Capsules, Elipses, Variants etc. | |
109 | * moving instead of copying + optimizations for movable/nonthrowing/trivialy copied elements | |
110 | * passing more than one nearest/path predicate - "returned value is one of k1 nearest values to p1 and ... and one of kN nearest values to pN" | |
111 | /] | |
112 | ||
113 | [heading Dependencies] | |
114 | ||
115 | R-tree depends on Boost.Container, Boost.Core, Boost.Move, Boost.MPL, Boost.Range, Boost.Tuple. | |
116 | ||
117 | [heading Contributors] | |
118 | ||
119 | The spatial index was originally started by Federico J. Fernandez during the Google Summer of Code 2008 program, mentored by Hartmut Kaiser. | |
120 | ||
121 | [heading Spatial thanks] | |
122 | ||
123 | I'd like to thank Barend Gehrels, Bruno Lalande, Mateusz Łoskot, Lucanus J. Simonson for their support and ideas. | |
124 | ||
125 | [endsect] | |
126 |