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.
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.
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