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 language | English (US) |
---|---|
Pages | 565-574 |
Number of pages | 10 |
State | Published - Dec 1 2009 |
Event | 25th Conference on Uncertainty in Artificial Intelligence, UAI 2009 - Montreal, QC, Canada Duration: Jun 18 2009 → Jun 21 2009 |
Other
Other | 25th Conference on Uncertainty in Artificial Intelligence, UAI 2009 |
---|---|
Country/Territory | Canada |
City | Montreal, QC |
Period | 6/18/09 → 6/21/09 |
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Applied Mathematics