Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?

Nakul Verma, Samory Kpotufe, Sanjoy Dasgupta
Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, PMLR R7:573-582, 2009.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR7-verma09a, title = {Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?}, author = {Verma, Nakul and Kpotufe, Samory and Dasgupta, Sanjoy}, booktitle = {Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence}, pages = {573--582}, year = {2009}, editor = {Bilmes, Jeff and Ng, Andrew Y.}, volume = {R7}, series = {Proceedings of Machine Learning Research}, month = {18--21 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r7/main/assets/verma09a/verma09a.pdf}, url = {https://proceedings.mlr.press/r7/verma09a.html}, 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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Which Spatial Partition Trees are Adaptive to Intrinsic Dimension? %A Nakul Verma %A Samory Kpotufe %A Sanjoy Dasgupta %B Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2009 %E Jeff Bilmes %E Andrew Y. Ng %F pmlr-vR7-verma09a %I PMLR %P 573--582 %U https://proceedings.mlr.press/r7/verma09a.html %V R7 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Verma, N., Kpotufe, S. & Dasgupta, S.. (2009). Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?. Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R7:573-582 Available from https://proceedings.mlr.press/r7/verma09a.html. Reissued by PMLR on 04 October 2026.

Related Material