1 /**
2  * @file core/tree/binary_space_tree/typedef.hpp
3  * @author Ryan Curtin
4  *
5  * Template typedefs for the BinarySpaceTree class that satisfy the requirements
6  * of the TreeType policy class.
7  *
8  * mlpack is free software; you may redistribute it and/or modify it under the
9  * terms of the 3-clause BSD license.  You should have received a copy of the
10  * 3-clause BSD license along with mlpack.  If not, see
11  * http://www.opensource.org/licenses/BSD-3-Clause for more information.
12  */
13 #ifndef MLPACK_CORE_TREE_BINARY_SPACE_TREE_TYPEDEF_HPP
14 #define MLPACK_CORE_TREE_BINARY_SPACE_TREE_TYPEDEF_HPP
15 
16 // In case it hasn't been included yet.
17 #include "../binary_space_tree.hpp"
18 
19 namespace mlpack {
20 namespace tree {
21 
22 /**
23  * The standard midpoint-split kd-tree.  This is not the original formulation by
24  * Bentley but instead the later formulation by Deng and Moore, which only holds
25  * points in the leaves of the tree.  When recursively splitting nodes, the
26  * KDTree class select the dimension with maximum variance to split on, and
27  * picks the midpoint of the range in that dimension as the value on which to
28  * split nodes.
29  *
30  * For more information, see the following papers.
31  *
32  * @code
33  * @article{bentley1975multidimensional,
34  *   title={Multidimensional binary search trees used for associative searching},
35  *   author={Bentley, J.L.},
36  *   journal={Communications of the ACM},
37  *   volume={18},
38  *   number={9},
39  *   pages={509--517},
40  *   year={1975},
41  *   publisher={ACM}
42  * }
43  *
44  * @inproceedings{deng1995multiresolution,
45  *   title={Multiresolution instance-based learning},
46  *   author={Deng, K. and Moore, A.W.},
47  *   booktitle={Proceedings of the 1995 International Joint Conference on AI
48  *       (IJCAI-95)},
49  *   pages={1233--1239},
50  *   year={1995}
51  * }
52  * @endcode
53  *
54  * This template typedef satisfies the TreeType policy API.
55  *
56  * @see @ref trees, BinarySpaceTree, MeanSplitKDTree
57  */
58 template<typename MetricType, typename StatisticType, typename MatType>
59 using KDTree = BinarySpaceTree<MetricType,
60                                StatisticType,
61                                MatType,
62                                bound::HRectBound,
63                                MidpointSplit>;
64 
65 /**
66  * A mean-split kd-tree.  This is the same as the KDTree, but this particular
67  * implementation will use the mean of the data in the split dimension as the
68  * value on which to split, instead of the midpoint.  This can sometimes give
69  * better performance, but it is not always clear which type of tree is best.
70  *
71  * This template typedef satisfies the TreeType policy API.
72  *
73  * @see @ref trees, BinarySpaceTree, KDTree
74  */
75 template<typename MetricType, typename StatisticType, typename MatType>
76 using MeanSplitKDTree = BinarySpaceTree<MetricType,
77                                         StatisticType,
78                                         MatType,
79                                         bound::HRectBound,
80                                         MeanSplit>;
81 
82 /**
83  * A midpoint-split ball tree.  This tree holds its points only in the leaves,
84  * similar to the KDTree and MeanSplitKDTree.  However, the bounding shape of
85  * each node is a ball, not a hyper-rectangle.  This can make the ball tree
86  * advantageous in some higher-dimensional situations and for some datasets.
87  * The tree construction algorithm here is the same as Omohundro's 'K-d
88  * construction algorithm', except the splitting value is the midpoint, not the
89  * median.  This can result in trees that better reflect the data, although they
90  * may be unbalanced.
91  *
92  * @code
93  * @techreport{omohundro1989five,
94  *   author={S.M. Omohundro},
95  *   title={Five balltree construction algorithms},
96  *   year={1989},
97  *   institution={University of California, Berkeley International Computer
98  *       Science Institute Technical Reports},
99  *   number={TR-89-063}
100  * }
101  * @endcode
102  *
103  * This template typedef satisfies the TreeType policy API.
104  *
105  * @see @ref trees, BinarySpaceTree, KDTree, MeanSplitBallTree
106  */
107 template<typename MetricType, typename StatisticType, typename MatType>
108 using BallTree = BinarySpaceTree<MetricType,
109                                  StatisticType,
110                                  MatType,
111                                  bound::BallBound,
112                                  MidpointSplit>;
113 
114 /**
115  * A mean-split ball tree.  This tree, like the BallTree, holds its points only
116  * in the leaves.  The tree construction algorithm here is the same as
117  * Omohundro's 'K-dc onstruction algorithm', except the splitting value is the
118  * mean, not the median.  This can result in trees that better reflect the data,
119  * although they may be unbalanced.
120  *
121  * @code
122  * @techreport{omohundro1989five,
123  *   author={S.M. Omohundro},
124  *   title={Five balltree construction algorithms},
125  *   year={1989},
126  *   institution={University of California, Berkeley International Computer
127  *       Science Institute Technical Reports},
128  *   number={TR-89-063}
129  * }
130  * @endcode
131  *
132  * This template typedef satisfies the TreeType policy API.
133  *
134  * @see @ref trees, BinarySpaceTree, BallTree, MeanSplitKDTree
135  */
136 template<typename MetricType, typename StatisticType, typename MatType>
137 using MeanSplitBallTree = BinarySpaceTree<MetricType,
138                                           StatisticType,
139                                           MatType,
140                                           bound::BallBound,
141                                           MeanSplit>;
142 
143 /**
144  * The vantage point tree (which is also called the metric tree. Vantage point
145  * trees and metric trees were invented independently by Yianilos an Uhlmann) is
146  * a kind of the binary space tree. When recursively splitting nodes, the VPTree
147  * class selects the vantage point and splits the node according to the distance
148  * to this point. Thus, points that are closer to the vantage point form the
149  * inner subtree. Other points form the outer subtree. The vantage point is
150  * contained in the first (inner) node.
151  *
152  * This implementation differs from the original algorithms. Namely, vantage
153  * points are not contained in intermediate nodes. The tree has points only in
154  * the leaves of the tree.
155  *
156  * For more information, see the following papers.
157  *
158  * @code
159  * @inproceedings{yianilos1993vptrees,
160  *   author = {Yianilos, Peter N.},
161  *   title = {Data Structures and Algorithms for Nearest Neighbor Search in
162  *       General Metric Spaces},
163  *   booktitle = {Proceedings of the Fourth Annual ACM-SIAM Symposium on
164  *       Discrete Algorithms},
165  *   series = {SODA '93},
166  *   year = {1993},
167  *   isbn = {0-89871-313-7},
168  *   pages = {311--321},
169  *   numpages = {11},
170  *   publisher = {Society for Industrial and Applied Mathematics},
171  *   address = {Philadelphia, PA, USA}
172  * }
173  *
174  * @article{uhlmann1991metrictrees,
175  *   author = {Jeffrey K. Uhlmann},
176  *   title = {Satisfying general proximity / similarity queries with metric
177  *       trees},
178  *   journal = {Information Processing Letters},
179  *   volume = {40},
180  *   number = {4},
181  *   pages = {175 - 179},
182  *   year = {1991},
183  * }
184  * @endcode
185  *
186  * This template typedef satisfies the TreeType policy API.
187  *
188  * @see @ref trees, BinarySpaceTree, VantagePointTree, VPTree
189  */
190 template<typename BoundType,
191          typename MatType = arma::mat>
192 using VPTreeSplit = VantagePointSplit<BoundType, MatType, 100>;
193 
194 template<typename MetricType, typename StatisticType, typename MatType>
195 using VPTree = BinarySpaceTree<MetricType,
196                                StatisticType,
197                                MatType,
198                                bound::HollowBallBound,
199                                VPTreeSplit>;
200 
201 /**
202  * A max-split random projection tree. When recursively splitting nodes, the
203  * MaxSplitRPTree class selects a random hyperplane and splits a node by the
204  * hyperplane. The tree holds points in leaf nodes. In contrast to the k-d tree,
205  * children of a MaxSplitRPTree node may overlap.
206  *
207  * @code
208  * @inproceedings{dasgupta2008,
209  *   author = {Dasgupta, Sanjoy and Freund, Yoav},
210  *   title = {Random Projection Trees and Low Dimensional Manifolds},
211  *   booktitle = {Proceedings of the Fortieth Annual ACM Symposium on Theory of
212  *       Computing},
213  *   series = {STOC '08},
214  *   year = {2008},
215  *   pages = {537--546},
216  *   numpages = {10},
217  *   publisher = {ACM},
218  *   address = {New York, NY, USA},
219  * }
220  * @endcode
221  *
222  * This template typedef satisfies the TreeType policy API.
223  *
224  * @see @ref trees, BinarySpaceTree, BallTree, MeanSplitKDTree
225  */
226 
227 template<typename MetricType, typename StatisticType, typename MatType>
228 using MaxRPTree = BinarySpaceTree<MetricType,
229                                   StatisticType,
230                                   MatType,
231                                   bound::HRectBound,
232                                   RPTreeMaxSplit>;
233 
234 /**
235  * A mean-split random projection tree. When recursively splitting nodes, the
236  * RPTree class may perform one of two different kinds of split.
237  * Depending on the diameter and the average distance between points, the node
238  * may be split by a random hyperplane or according to the distance from the
239  * mean point. The tree holds points in leaf nodes. In contrast to the k-d tree,
240  * children of a MaxSplitRPTree node may overlap.
241  *
242  * @code
243  * @inproceedings{dasgupta2008,
244  *   author = {Dasgupta, Sanjoy and Freund, Yoav},
245  *   title = {Random Projection Trees and Low Dimensional Manifolds},
246  *   booktitle = {Proceedings of the Fortieth Annual ACM Symposium on Theory of
247  *       Computing},
248  *   series = {STOC '08},
249  *   year = {2008},
250  *   pages = {537--546},
251  *   numpages = {10},
252  *   publisher = {ACM},
253  *   address = {New York, NY, USA},
254  * }
255  * @endcode
256  *
257  * This template typedef satisfies the TreeType policy API.
258  *
259  * @see @ref trees, BinarySpaceTree, BallTree, MeanSplitKDTree
260  */
261 template<typename MetricType, typename StatisticType, typename MatType>
262 using RPTree = BinarySpaceTree<MetricType,
263                                   StatisticType,
264                                   MatType,
265                                   bound::HRectBound,
266                                   RPTreeMeanSplit>;
267 
268 /**
269  * The Universal B-tree. When recursively splitting nodes, the class
270  * calculates addresses of all points and splits each node according to the
271  * median address. Children may overlap since the implementation
272  * of a tighter bound requires a lot of arithmetic operations. In order to get
273  * a tighter bound increase the CellBound::maxNumBounds constant.
274  *
275  * @code
276  * @inproceedings{bayer1997,
277  *   author = {Bayer, Rudolf},
278  *   title = {The Universal B-Tree for Multidimensional Indexing: General
279  *       Concepts},
280  *   booktitle = {Proceedings of the International Conference on Worldwide
281  *       Computing and Its Applications},
282  *   series = {WWCA '97},
283  *   year = {1997},
284  *   isbn = {3-540-63343-X},
285  *   pages = {198--209},
286  *   numpages = {12},
287  *   publisher = {Springer-Verlag},
288  *   address = {London, UK, UK},
289  * }
290  * @endcode
291  *
292  * This template typedef satisfies the TreeType policy API.
293  *
294  * @see @ref trees, BinarySpaceTree, BallTree, MeanSplitKDTree
295  */
296 template<typename MetricType, typename StatisticType, typename MatType>
297 using UBTree = BinarySpaceTree<MetricType,
298                                StatisticType,
299                                MatType,
300                                bound::CellBound,
301                                UBTreeSplit>;
302 
303 } // namespace tree
304 } // namespace mlpack
305 
306 #endif
307