Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?

Nakul Verma, Samory Kpotufe, Sanjoy Dasgupta

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.

Introduction

Spatial partition trees are fundamental tools in machine learning, used to recursively divide data into cells for efficient processing. However, traditional structures like k-d trees often suffer from the "curse of dimensionality." In a $D$-dimensional space, these trees may require $2^D$ data points just to halve the diameter of a cell, making them impractical for high-dimensional inputs.

Fortunately, real-world high-dimensional data—such as images, sensor logs, or speech—often resides on a low-dimensional manifold with an intrinsic dimension $d \ll D$. This paper investigates which tree structures can ignore ambient noise and adapt their splitting strategies to this hidden, low-dimensional structure.

Spatial Partitioning Strategies

The authors evaluate five distinct tree types, categorized by their splitting rules:

  1. Dyadic trees: Splits occur at the midpoint of coordinate axes in a fixed cycle.
  2. k-d trees: Splits occur at the median along the coordinate axis with the largest spread.
  3. Random Projection (RP) trees: Splits occur at the median along a randomly chosen direction.
  4. Principal Direction (PD/PCA) trees: Splits occur at the median along the principal eigenvector (direction of maximum variance).
  5. 2-Means (2M) trees: Splits are determined by a 2-means clustering assignment.
Comparison of partitioning strategies: axis-aligned (left/middle) vs. adaptive oblique splits (right).

While dyadic and k-d trees are restricted to axis-parallel splits, PD and 2M trees utilize oblique splits that can better align with the data's local geometry.

Measuring Intrinsic Dimension

To quantify adaptivity, the researchers introduce the Local Covariance Dimension. This metric assesses the number of dimensions required to capture the majority of data variance within a local neighborhood. By analyzing the eigenspectrum of local covariance matrices, one can estimate the intrinsic dimension $d$ across various scales (radii).

Local dimension estimates for the Swissroll and Teapot datasets across varying radii.

As shown in the figures above, the estimated local dimension for complex datasets like the "Rotating Teapot" (ambient $D=1500$) remains significantly lower than their ambient dimensions, confirming the presence of exploitable low-dimensional structure.

Key Insights and Results

The study yields several critical findings regarding tree performance:

  • PCA and 2-Means Superiority: PD and 2M trees provide the strongest theoretical bounds. They adapt not just to the dimension $d$, but to the specific eigenspectrum of the data. By seeking directions of maximum variance, they exploit local "flatness" more effectively than RP trees.
  • Failure of Axis-Parallel Splits: k-d and dyadic trees are constrained by the coordinate system. If a manifold is tilted relative to the axes, these trees require significantly more splits to "wrap" around the data, leading to slower convergence.
  • Performance in Downstream Tasks: On the Teapot (1500D) and Robotic Arm (12D) datasets, 2M and PD trees consistently achieved the lowest errors in vector quantization and regression. They reached low error rates at much shallower depths than k-d trees.
  • Nearest Neighbor Search: Adaptive trees organize space more meaningfully, finding "closer" neighbors at equivalent tree depths compared to non-adaptive counterparts.

Conclusion

While k-d trees are computationally cheaper to build, they fail to scale with the intrinsic dimension of data. PCA-based and 2-means trees, despite higher construction costs, offer superior adaptivity to low-dimensional manifolds. For high-dimensional datasets with latent structure, these adaptive spatial partitions are essential for efficient and accurate statistical inference.

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