{
  "id": "1205.2609",
  "version": "v1",
  "published": "2012-05-09T18:37:50.000Z",
  "updated": "2012-05-09T18:37:50.000Z",
  "title": "Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?",
  "authors": [
    "Nakul Verma",
    "Samory Kpotufe",
    "Sanjoy Dasgupta"
  ],
  "comment": "Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI2009)",
  "categories": [
    "stat.ML",
    "cs.LG"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-05-09T18:37:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "spatial partition tree",
      "intrinsic dimension",
      "intrinsic low dimensional structure",
      "random projection tree",
      "nearest neighbor search"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1205.2609V"
    }
  }
}