The hubness problem is a phenomenon mentioned in this paper, for instance. It claims that for random data point clouds in high-dimensional spaces, there will be "many" hubs -- that is, points that are within k nearest neighbors of many other points.
We define, for each point $x$, the number $N_k(x)$ to be the number of other points $y$ such that $x$ belongs to $k$ nearest members of $y$. Radonovic claims that $N_k(x)$ has approximately normal distribution for random point clouds in low dimensional manifolds, but a highly skewed distribution with long right-tail in high dimensions. Radonovic illustrates this with uniformly distributed points in $[0,1]^N$.
I tried to reproduce some of that in Python and came to a surprising observation. While the $N_k(x)$ distribution is indeed skewed in high dimensions when generating uniform point cloud in the cube and using the Euclidean distance function, I didn't observe this when generating uniform point clouds in the sphere.
Experiment with a cube (uniformly generated 2000 points in $[0,1]^{500}$)
The same experiment with a sphere (uniformly generated 2000 points in $S^{500}$)
My intuition is that there should be no difference between hub-histograms in an $n$-cube or an $n$-sphere, because this hubeness seems to be a local phenomenon. Unless I have some stupid mistake in the code, my intuition seems to be wrong.
Generating more points, I think I could see some skewness in the sphere as well, but only very slightly, if at all.
So here are my questions:
- How is the cube different from a sphere? Could the difference be only explained by boundaries, corners or corners of corners?
- Any insight into this hubeness-phenomena?