New Instability Results for High Dimensional Nearest Neighbor Search

Details New Instability Results for High Dimensional Nearest Neighbor Search New Instability Results for High Dimensional Nearest Neighbor Search

2009-06-03

arxiv.org/abs/0906.0684v1

Information Processing Letters 109(19), 2009.

Computer Science

Databases

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

New Instability Results for High Dimensional Nearest Neighbor Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New Instability Results for High Dimensional Nearest Neighbor Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Instability Results for High Dimensional Nearest Neighbor Search will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-193907