Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
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"
}


hosted by DSL   •   site info   •   help