is not possible to quickly reject candidates by using the difference in one coordinate as a lower bound for a distance based on all the dimensions. However, it has recently been observed that the mere number of dimensions does not necessarily result in difficulties, since relevant additional dimensions can also increase the contrast. In addition, for the resulting ranking it remains useful to discern close and far neighbors. Irrelevant ("noise") dimensions, however, reduce the contrast in the manner described above. In time series analysis, where the data are inherently high-dimensional, distance functions also work reliably as long as the signal-to-noise ratio is high enough. k-nearest neighbor classification Another effect of high dimensionality on distance functions concerns k-nearest neighbor (k-NN) graphs constructed from a data set using a distance function. As the dimension increases, the indegree distribution of the k-NN digraph becomes skewed with a peak on the right because of the emergence of a disproportionate number of hubs, that is, data-points that appear in many more k-NN lists of other data-points than the average. This phenomenon can have a considerable impact on various techniques for classification (including the k-NN classifier), semi-supervised learning, and clustering, and it also affects information retrieval. Anomaly detection In a 2012 survey, Zimek et al. identified the following problems when searching for anomalies in high-dimensional data: Concentration of scores and distances: derived values such as distances become numerically similar Irrelevant attributes: in high dimensional data, a significant number of attributes may be irrelevant Definition of reference sets: for local methods, reference sets are often nearest-neighbor based Incomparable scores for different dimensionalities: different subspaces produce incomparable scores Interpretability of scores: the scores often no longer convey a semantic meaning Exponential search space: the search space can no longer be systematically scanned Data snooping bias: given the large search space, for every desired significance a hypothesis can be found Hubness: certain objects occur more frequently in neighbor lists than others. Many of the analyzed specialized methods tackle one or another of these problems, but there remain many open research questions. Blessing of dimensionality Surprisingly and despite the expected "curse of dimensionality" difficulties, common-sense heuristics based on the most straightforward methods "can yield results which are almost surely optimal" for high-dimensional problems. The term "blessing of dimensionality" was introduced in the late 1990s. Donoho in his "Millennium manifesto" clearly explained why the "blessing of dimensionality" will form a basis