7798

Approximate Principal Direction Trees

Mark McCartin-Lim, Andrew McGregor, Rui Wang
University of Massachusetts Amherst, 140 Governors Drive, Amherst, MA 01002-9264 USA
arXiv:1206.4668v1 [cs.LG] (18 Jun 2012)

@article{2012arXiv1206.4668M,

   author={McCartin-Lim}, M. and {McGregor}, A. and {Wang}, R.},

   title={"{Approximate Principal Direction Trees}"},

   journal={ArXiv e-prints},

   archivePrefix={"arXiv"},

   eprint={1206.4668},

   primaryClass={"cs.LG"},

   keywords={Computer Science – Learning, Computer Science – Data Structures and Algorithms, Statistics – Machine Learning},

   year={2012},

   month={jun},

   adsurl={http://adsabs.harvard.edu/abs/2012arXiv1206.4668M},

   adsnote={Provided by the SAO/NASA Astrophysics Data System}

}

Download Download (PDF)   View View   Source Source   

836

views

We introduce a new spatial data structure for high dimensional data called the emph{approximate principal direction tree} (APD tree) that adapts to the intrinsic dimension of the data. Our algorithm ensures vector-quantization accuracy similar to that of computationally-expensive PCA trees with similar time-complexity to that of lower-accuracy RP trees. APD trees use a small number of power-method iterations to find splitting planes for recursively partitioning the data. As such they provide a natural trade-off between the running-time and accuracy achieved by RP and PCA trees. Our theoretical results establish a) strong performance guarantees regardless of the convergence rate of the power-method and b) that $O(log d)$ iterations suffice to establish the guarantee of PCA trees when the intrinsic dimension is $d$. We demonstrate this trade-off and the efficacy of our data structure on both the CPU and GPU.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: