Why is the curse of dimensionality also called the empty space phenomenon? The curse of dimensionality refers to the fact that the huge number of correlated features tends to increase the complexity of the treatment that has to be applied to the data set. This is also called the empty space phenomenon. So, does anyone know the relation between those two? 
 A: I don't think the curse of dimensionality has anything to do with correlation, or at least not in my understanding.  The curse is the notion that a local neighborhood of a point in a high dimensional space is not really so local - the number of data points it takes to uniformly "fill" a neighborhood of a point with a fixed volume (think a unit cube centered at that point) grows exponentially with the dimension.  Conversely, if you have a fixed number of points, and increase the dimension of the space that they reside in, you will very quickly find yourself in the situation where most of your space is empty.
This comes up, for example, in $k$ nearest neighbors classification.  Here we attempt to classify a new point by searching for the $k$ training points closest to it.  In small dimensions, which is what people have concrete experience with and hence hence intuition for, these $k$ points all tend to be close by, as the entire space is is rather densely populated with training examples.  But in large dimensions, the intuition fails - the $k$ nearest points tend to be quite far away, with much empty space in between.

Suppose the dimension of the input space is 100 and we have a huge training set of a trillion (10^{12}) examples, then the examples will cover only a fraction of about 10^{-18} of the input space. Can anyone explain to me why is that?

Here's a short explanation of what that may be getting at.  Let's suppose all of our features are binary, this simplifies that math but is not essential.  Then there are $2^{100}$ possible combinations of features.  Now $\log_2(10^{12}) \approx 40$, that is $10^{12} \approx 2^{40}$, so the proportion of feature combinations "unaccounted for" is approximately $\frac{2^{100}}{2^{40}} = 2^{60}$.  Now just observe that $\log_{10}(2^{60}) \approx 18$, so $2^{60} \approx 10^{18}$.
