ML Anthology

Random Projection Trees Revisited

Aman Dhesi, Purushottam Kar
NeurIPS 2010 pp. 496-504
/neurips/2010/dhesi2010neurips-random/

Abstract

The Random Projection Tree (RPTree) structures proposed in [Dasgupta-Freund-STOC-08] are space partitioning data structures that automatically adapt to various notions of intrinsic dimensionality of data. We prove new results for both the RPTree-Max and the RPTree-Mean data structures. Our result for RPTree-Max gives a near-optimal bound on the number of levels required by this data structure to reduce the size of its cells by a factor s >= 2. We also prove a packing lemma for this data structure. Our final result shows that low-dimensional manifolds possess bounded Local Covariance Dimension. As a consequence we show that RPTree-Mean adapts to manifold dimension as well.

PDF NeurIPS Semantic Scholar

Cite

Text

Dhesi and Kar. "Random Projection Trees Revisited." Neural Information Processing Systems, 2010.

Markdown

[Dhesi and Kar. "Random Projection Trees Revisited." Neural Information Processing Systems, 2010.](https://mlanthology.org/neurips/2010/dhesi2010neurips-random/)

BibTeX

@inproceedings{dhesi2010neurips-random,
  title     = {{Random Projection Trees Revisited}},
  author    = {Dhesi, Aman and Kar, Purushottam},
  booktitle = {Neural Information Processing Systems},
  year      = {2010},
  pages     = {496-504},
  url       = {https://mlanthology.org/neurips/2010/dhesi2010neurips-random/}
}