|
|
|
|
Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?
Nakul Verma, Samory Kpotufe, Sanjoy Dasgupta
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.
Keywords: null
Pages: 565-574
PS Link:
PDF Link: /papers/09/p565-verma.pdf
BibTex:
@INPROCEEDINGS{Verma09,
AUTHOR = "Nakul Verma
and Samory Kpotufe and Sanjoy Dasgupta",
TITLE = "Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?",
BOOKTITLE = "Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2009",
PAGES = "565--574"
}
|
|
