The Hubness Phenomenon in High-Dimensional Spaces

High-dimensional data analysis is often negatively affected by the curse of dimensionality. In high-dimensional spaces, data becomes extremely sparse and distances between points become indistinguishable. As a consequence, reliable estimations of density, or meaningful distance-based similarity measures, cannot be obtained. This issue is particularly prevalent in clustering, which is commonly employed in exploratory data analysis. Another challenge for clustering high-dimensional data is that data often exist in subspaces consisting of combinations of dimensions, with different subspaces being relevant for different clusters. The hubness phenomenon is a recently discovered aspect of high-dimensional spaces. It is observed that the distribution of neighbor occurrences becomes skewed in intrinsically high-dimensional data, with few points, the hubs, having high occurrence counts. Hubness is observed to be more pronounced with increasing dimensionality. Hubs are also known to exhibit useful clustering properties and could be leveraged to mitigate the challenges in high-dimensional data analysis. In this chapter, we identify new geometric relationships between hubness, data density, and data distance distribution, as well as between hubness, subspaces, and intrinsic dimensionality of data. In addition, we formulate various potential research directions to leverage hubness for clustering and for subspace estimation.