Which spatial partition trees are adaptive to intrinsic dimension?

Nakul Verma, Samory K. Kpotufe, Sanjoy Dasgupta

Research output: Contribution to conferencePaper

43 Scopus citations

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.

Original languageEnglish (US)
Pages565-574
Number of pages10
StatePublished - Dec 1 2009
Event25th Conference on Uncertainty in Artificial Intelligence, UAI 2009 - Montreal, QC, Canada
Duration: Jun 18 2009Jun 21 2009

Other

Other25th Conference on Uncertainty in Artificial Intelligence, UAI 2009
CountryCanada
CityMontreal, QC
Period6/18/096/21/09

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Which spatial partition trees are adaptive to intrinsic dimension?'. Together they form a unique fingerprint.

  • Cite this

    Verma, N., Kpotufe, S. K., & Dasgupta, S. (2009). Which spatial partition trees are adaptive to intrinsic dimension?. 565-574. Paper presented at 25th Conference on Uncertainty in Artificial Intelligence, UAI 2009, Montreal, QC, Canada.