Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2012
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1205.2609 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913757933862912 |
|---|---|
| author | Verma, Nakul Kpotufe, Samory Dasgupta, Sanjoy |
| author_facet | Verma, Nakul Kpotufe, Samory Dasgupta, Sanjoy |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1205_2609 |
| institution | arXiv |
| publishDate | 2012 |
| record_format | arxiv |
| spellingShingle | Which Spatial Partition Trees are Adaptive to Intrinsic Dimension? Verma, Nakul Kpotufe, Samory Dasgupta, Sanjoy Machine Learning 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. |
| title | Which Spatial Partition Trees are Adaptive to Intrinsic Dimension? |
| topic | Machine Learning |
| url | https://arxiv.org/abs/1205.2609 |