Random Projection Trees Revisited

The Curse of Dimensionality [2] has inspired research in several directions in Computer Science and has led to the development of several novel techniques such as dimensionality reduction, sketching etc. Almost all these techniques try to map data to lower dimensional spaces while approximately preserving useful information. However, most of these techniques do not assume anything about the data other than that they are are imbedded in some high dimensional Euclidean space endowed with some distance/similarity function. As it turns out, in many situations, the data is not simply scattered in the Euclidean space in a random fashion. Often, generative processes impose (nonlinear) dependencies on the data that restrict the degrees of freedom available and result in the data having low intrinsic dimensionality. There exist several formalizations of this concept of intrinsic dimensionality.