Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?
This work addresses the problem of improving efficiency in statistical tasks for researchers and practitioners by exploring if common spatial partition trees can adapt to intrinsic data dimensionality, though it appears incremental as it extends prior findings on random projection trees.
The paper investigates whether spatial partition trees like k-d trees, dyadic trees, and PCA trees are adaptive to the intrinsic dimension of data, combining theory and experiments to assess their ability to exploit low-dimensional structure for tasks such as regression, vector quantization, and nearest neighbor search.
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.