Nearest Neighbors in High-Dimensional Data: The Emergence and Influence of Hubs

High dimensionality can pose severe difficulties, widely recognized as different aspects of the curse of dimensionality. In this paper we study a new aspect of the curse pertaining to the distribu