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