Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?

Nakul Verma, Samory Kpotufe, Sanjoy Dasgupta

Introduction

In high-dimensional machine learning, the "curse of dimensionality" often renders standard data structures inefficient. While ambient dimensions ($D$) can be large, real-world data frequently resides on low-dimensional manifolds with an intrinsic dimension $d \ll D$. This paper explores which spatial partitioning trees can effectively ignore ambient noise and adapt to this underlying structure.

Spatial Partitioning Strategies

The authors evaluate several tree-building rules based on their splitting criteria. Standard k-d trees and dyadic trees use axis-aligned splits, which can be inefficient when the manifold is not aligned with the coordinate axes. In contrast, Random Projection (RP) trees, Principal Direction (PD/PCA) trees, and Two-Means (2M) trees employ more flexible, non-axis-aligned partitions.

Comparison of spatial partitioning strategies: standard axis-aligned splits (left and middle) versus adaptive, non-axis-aligned splits (right).

PD trees split data along the direction of maximum variance (the principal eigenvector), while 2M trees split based on a 2-means clustering assignment. These "greedy" approaches are designed to collapse cell diameters faster by identifying the directions of greatest data spread.

Quantifying Adaptivity

To formalize adaptivity, the authors introduce the Local Covariance Dimension $(d, \epsilon)$. A neighborhood has a low covariance dimension if its top $d$ eigenvalues account for the vast majority of its variance. This metric allows for a multi-scale analysis of data dimensionality across different radii.

Local dimension estimates across different radii for the Swissroll, Teapot, and Robotic Arm datasets, illustrating the multi-scale nature of intrinsic dimensionality.

Key Insights and Results

The core finding is that PD and 2-Means trees are significantly more adaptive than k-d trees. Theoretically, the authors prove that for PD trees, the rate of diameter shrinkage becomes independent of the ambient dimension $D$ once the tree "finds" the local manifold.

Empirically, these adaptive trees outperform k-d trees in several tasks:

  • Vector Quantization & Regression: On high-dimensional datasets like the 1500-D Teapot images, PD and 2M trees reduced regression error much faster than axis-aligned methods.
  • Nearest Neighbor Search: Adaptive trees consistently found closer neighbors at shallower depths compared to standard methods.

Conclusion

While computationally more expensive to construct due to eigenvalue decompositions or iterative clustering, PD and 2-Means trees offer superior performance for high-dimensional data with low intrinsic dimensionality. They successfully bypass the curse of dimensionality by focusing on the directions that matter most for the data's actual structure.

Summary updated

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.
BibTeX
@inproceedings{verma2009which,
  author = {Nakul Verma and Samory Kpotufe and Sanjoy Dasgupta},
  title = {{Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=0w3OGdFoZKv},
}
Figure