New instability results for high-dimensional nearest neighbor search
From MaRDI portal
(Redirected from Publication:990934)
Abstract: 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).
Recommendations
- Instability results for Euclidean distance, nearest neighbor search on high dimensional Gaussian data
- Exact \(L_{\infty}\) nearest neighbor search in high dimensions
- scientific article; zbMATH DE number 2065612
- When is `nearest neighbour' meaningful: A converse theorem and implications
- scientific article; zbMATH DE number 1559575
Cites work
- scientific article; zbMATH DE number 2080487 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- A Strong Law for the Largest Nearest-Neighbour Link between Random Points
- Bounds on the mean power-weighted nearest neighbour distance
- Concentration of measure and cluster analysis.
- On the geometry of similarity search: dimensionality curse and concentration of measure
- Probability Inequalities for Sums of Bounded Random Variables
- Volume of unit ball in an n-dimensional normed space and its asymptotic properties
Cited in
(5)- On the behavior of intrinsically high-dimensional spaces: distances, direct and reverse nearest neighbors, and hubness
- Instability results for Euclidean distance, nearest neighbor search on high dimensional Gaussian data
- On the distance concentration awareness of certain data reduction techniques
- Non-parametric detection of meaningless distances in high dimensional data
- Intrinsic dimension of geometric data sets
This page was built for publication: New instability results for high-dimensional nearest neighbor search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990934)
