What Is the Nearest Neighbor in High Dimensional Spaces?

By Alexander Hinneburg, Charu C. Aggarwal, Daniel A. Keim. Very Large Data Bases Conference, 2000

651 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/9c5984594b6cb2a0bf227bf1142f49572cfcf842

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data (2010, background): “dimensions has been thoroughly explored (Beyer et al., 1999; Hinneburg et al., 2000; Aggarwal et al., 2001; François et al., 2007).”
A review of content-based image retrieval systems in medical applications - clinical benefits and future directions (2004, background): “Still, the use of high–dimensional feature spaces has shown to cause problems and great care needs to be taken with the choice of distance measurement to be chosen in order to retrieve meaningful results [61, 62].”
Distance geometry and data science (2019, methodology): “…of distance matrices (Cayley 1841), Maxwell’s analysis of the stiffness of frames (Maxwell 1864), Henneberg’s investigations on rigidity of structures (Henneberg 1911), Gödel’s fixed point theorem for showing that a tetrahedron with nonzero volume can be embedded isometrically (with geodetic…”
Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data (2009, unknown): “[2]).”
A Monte Carlo algorithm for fast projective clustering (2002, unknown): “close as its nearest neighbor [8].”
Feature selection for text classification: A review (2018, background): “Similar behavior can be observed for Lp distance metrics such as Manhattan distance (L1), L3 distance, and general Lk metrics [37].”
Angle-based outlier detection in high-dimensional data (2008, background): “Copyright 2008 ACM 978-1-60558-193-4/08/08 ...$5.00. disturbance impairing the sensors, or simply incorrect reading of the measurement equipment.”
On the Surprising Behavior of Distance Metrics in High Dimensional Spaces (2001, background): “Our recent results [9] seem to suggest that the Lk-norm may be more relevant for k = 1 or 2 than values of k 3.”
Divergence Estimation for Multidimensional Densities Via $k$-Nearest-Neighbor Distances (2009, background): “Hinneburg et al. [17] put forward a new notion of NN search, which does not treat all dimensions equally but uses a quality criterion to select relevant dimensions with respect to a given query.”
SMOTE for high-dimensional class-imbalanced data (2013, unknown): “Similar results were described by others [33,34].”
Locality-sensitive hashing scheme based on p-stable distributions (2004, background): “In fact, in situations when the quality of the approx imate nearest neighbor is much worse than the quality of the actual nearest neighbor, then the nearest neighbor problem is unstable, and it is not clear if solving it is at all meaningful [4, 17].”
The Concentration of Fractional Distances (2007, background): “Some literature suggests using fractional norms, an extension of the euclidean norm, to counter concentration effects [23], [24].”
The Challenges of Clustering High Dimensional Data (2004, background): “The work just discussed was extended in [ HAK00 ] to look at the absolute difference, MaxDist – MinDist, instead of the relative difference.”
Outlier Analysis (2013, methodology): “On the other hand, it has been shown in [65, 215], that all pairs of points are almost equidistant in high-dimensional space.”