Random Projection Trees are a special type of recursive space partitioning datastructure,
which can automatically adapt to the underlying (linear or non-linear)
structure in data. They have strong theoretical guarantees on rates
of convergence and work well in practice.
You can use RPTrees to learn the structure of manifolds, perform
fast nearest-neighbor searches, do vector-quantization of the underlying
density, and much more.
To learn more, go the tutorials page,
or see the full publication.