New instability results for high-dimensional nearest neighbor search

Consider a dataset of n(d) points generated independently from Rd according to a common p.d.f. fd with support(fd)=d[0,1] and sup{fd(Rd)} growing sub-exponentially in d. We prove that: (i) if n(d) grows sub-exponentially in d, then, for any query point and any ϵ>0, the ratio of the distance between any two dataset points and is less that 1+ϵ with probability →1 as d→∞; (ii) if n(d)>d[4(1+ϵ)] for large d, then for all (except a small subset) and any ϵ>0, the distance ratio is less than 1+ϵ with limiting probability strictly bounded away from one. Moreover, we provide preliminary results along the lines of (i) when .