# Generating a high-dimensional dataset where nearest neighbor becomes meaningless

In the paper "When Is 'Nearest Neighbor' Meaningful?" we read that,

We show that under certain broad conditions (in terms of data and query distributions, or workload), as dimensionality increases, the distance to the nearest neighbor approaches the distance to the farthest neighbor. In other words, the contrast in distances to different data points becomes nonexistent. The conditions we have identied in which this happens are much broader than the independent and identically distributed (IID) dimensions assumption that other work assumes.

My question is, how I should generate a dataset that produces this effect?

I have created three points each with 1000 dimensions with random numbers ranging from 0-255 for each dimension but points create different distances and do not reproduce what is mentioned above. It seems changing dimensions (e.g. 10 or 100 or 1000 dimensions) and ranges (e.g. [0,1]) do not change anything. I still get different distances which should not be any problem for e.g. clustering algorithms!

Edit: I have tried more samples, based on my experiments distances between points do not converge to any number, on the contrary the max and min distances between points get more apparent. This is also in contrary to what is written in the first post of Need more intuition for the curse of dimensionality and also many other places which claim the same thing like https://en.wikipedia.org/wiki/Clustering_high-dimensional_data#Problems. I would still appreciate it if someone can show me with a piece of code or real dataset that such effect exist in practical scenarios.

• 100 dimensions would already count as very high dimensional (compared to the 2, 3 or perhaps 4 dimensional real world applications that euclidean distances are originally used for). Don't expect much change between 100 and 1000. Distances are different, OK but by how much? Dec 27, 2016 at 11:00
• Distance is different in meaningful ways even for 1 million dimensions. Now that I think about it, maybe my random number generation is the problem. Right now I'm simply generating random numbers in a specific range and dedicating them to each dimension but I think a more accurate approach is to use something like multivariate normal distribution to produce random numbers.
– U66
Dec 27, 2016 at 11:13
• I used multivariate normal distribution of apache common and still cannot replicate the effect!!!
– U66
Dec 28, 2016 at 5:08

Read some of the newer follow-up articles, such as:

Houle, M. E., Kriegel, H. P., Kröger, P., Schubert, E., & Zimek, A. (2010, June). Can shared-neighbor distances defeat the curse of dimensionality?. In International Conference on Scientific and Statistical Database Management (pp. 482-500). Springer Berlin Heidelberg.

and

Zimek, A., Schubert, E., & Kriegel, H. P. (2012). A survey on unsupervised outlier detection in high‐dimensional numerical data. Statistical Analysis and Data Mining, 5(5), 363-387.

If I remember correctly, they show the properties of the theoretical distance concentration effect (which is proven) and the limitations why reality may behave very different. If these articles aren't helpful, ping me and I recheck the references (just typed what I remembered into Google Scholar, I didn't download the papers again).

Beware that the "curse" does not say the difference of distances to the nearest and farthest neighbors approaches 0; nor that the distances would converge to some number. but rather that the relative difference compared to the absolute value becomes small. Then random deviations can cause neighbors to be incorrectly ranked.

In this equartion, don't ignore the fraction, expected value, and $d\rightarrow\infty$: $$\lim_{d \to \infty} E\left(\frac{\operatorname{dist}_{\max} (d) - \operatorname{dist}_{\min} (d)}{\operatorname{dist}_{\min} (d)}\right) \to 0$$

• Hi, thanks for the information, the main question still remains unanswered though that how we can generate a sample that resembles this effect?Also, I didn't quite get this sentence "relative difference compared to the absolute value" can you explain more?
– U66
Jan 1, 2017 at 10:52
• hmmm...I think I could replicate the effect successfully, the point is in the division (e.g. it is the relative distance of (max-min) to the minimum point and not the simple distances). As I increased the dimensions the relative distance becomes smaller. This is true for origin and also any other points in the dataset.
– U66
Jan 1, 2017 at 13:59
• "Relative distance" refers exactly to this division. It's fairly clear that the absolute values do not converge to a constant. Jan 1, 2017 at 15:36

I hadn't heard of this before either, so I am little defensive, since I have seen that real and synthetic datasets in high dimensions really do not support the claim of the paper in question.

As a result, what I would suggest, as a first, dirty, clumsy and maybe not good first attempt is to generate a sphere in a dimension of your choice (I do it like like this) and then place a query at the center of the sphere.

In that case, every point lies in the same distance with the query point, thus the Nearest Neighbor has a distance equal to the Farthest Neighbor.

This, of course, is independent from the dimension, but it's what came at a thought after looking at the figures of the paper. It should be enough to get you stared, but surely, better datasets may be generated, if any.

Theorem 5: If $$X^{(d)}=(X_1 \dots X_d) \in \mathbb{R}^d$$ is a $$d$$ -dimensional random vector with iid components, then $$\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1 \iff Var\left[\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||}\right] \to 0, d \to \infty.$$
So this means that if your generated iid random sample by using a random vector whose components are iid (e.g. a normal $$\mathcal{N}(0, I_d)$$ random vector), then its "relative variance $$Var\left[\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||}\right]$$" will go to zero, and hence by Beyer's theorem the maximum norm (=distance to the query point as the origin) divided by minimum norm (=distance to the query point as origin) will converge in probability to $$1,$$ or equivalently the "relative contrast" (the ratio mentioned in Anony-Mousse's answer above, with query point the origin, i.e. ratio of the distances between the farthest and nearest point, minus one) wil go to zero as well.