Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?
By Nakul Verma, Samory Kpotufe, Sanjoy Dasgupta. 2009
85 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Michael J. Kane
- Peter Bhlmann
- Petros Drineas
- M. J. van der Laan
- Qiang Yue
- Yuxiang Wang
- Mengzhao Wang
- Xiaoliang Xu
In Computational Theory and Mathematics
- Peter Bhlmann
- Michael J. Kane
- M. J. van der Laan
- Petros Drineas
- Michael W. Mahoney
- David P. Woodruff
- Kenneth L. Clarkson
In Signal Processing
- Peter Bhlmann
- M. J. van der Laan
- Michael J. Kane
- Petros Drineas
- Qiang Yue
- Yuxiang Wang
- Mengzhao Wang
- Xiaoliang Xu
Citations in the corpus
- Handbook of Big Data (2016, background): “Some further work along these lines was done in [1,41,93].”
- A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, methodology): “SPTAG previously adopts a random division scheme, which generates the principal directions over points randomly sampled from S , then performs random divisions to make each subset’s diameter small enough [95, 100].”