Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?

Abstract

Recent theory work has found that a special type of spatial partition tree - called a random projection tree - is adaptive to the intrinsic dimension of the data from which it is built. Here we examine this same question, with a combination of theory and experiments, for a broader class of trees that includes k-d trees, dyadic trees, and PCA trees. Our motivation is to get a feel for (i) the kind of intrinsic low dimensional structure that can be empirically verified, (ii) the extent to which a spatial partition can exploit such structure, and (iii) the implications for standard statistical tasks such as regression, vector quantization, and nearest neighbor search.

Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI2009)

References in corpus (1)

• Escaping the curse of dimensionality with a tree-based regressor

Cited by in corpus (11)

• Geometric deep learning: going beyond Euclidean data
• Neural Decision Trees
• Approximate Principal Direction Trees
• Spectral Approaches to Nearest Neighbor Search
• Scalable Nearest Neighbor Search based on kNN Graph
• On Semi-parametric Bernstein-von Mises Theorems for BART
• Scalable $k$-NN graph construction
• Fast k-means based on KNN Graph
• Efficient Hierarchical Clustering for Classification and Anomaly Detection
• Geometry Aware Mappings for High Dimensional Sparse Factors
• Particle Filtering on the Audio Localization Manifold