What is Nearest neighbor: Definition and 11 Discussions

Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values.
Formally, the nearest-neighbor (NN) search problem is defined as follows: given a set S of points in a space M and a query point q ∈ M, find the closest point in S to q. Donald Knuth in vol. 3 of The Art of Computer Programming (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a k-NN search, where we need to find the k closest points.
Most commonly M is a metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, M is taken to be the d-dimensional vector space where dissimilarity is measured using the Euclidean distance, Manhattan distance or other distance metric. However, the dissimilarity function can be arbitrary. One example is asymmetric Bregman divergence, for which the triangle inequality does not hold.

View More On Wikipedia.org
  1. T

    New Nearest Neighbor & Sorting approach

    Finding the Nearest Neighbor in a dataset has always been considered difficult, needing data-specific coding. Now some researchers, trying to prove there is no universal approach, say they have found one. This first link is to the 'popular' article...
  2. qnach

    Nearest neighbour, nnn....etc. of an atom in a crystal

    There are some software can provide visualization of crystal or protein structure, i.e. VESTA. I want to know how many atoms is the nearest neightbour (and their distance), and the next nearest neighbour...etc of a particular atom. Is there any software (or perhaps some data book?) can do this?
  3. Adoniram

    Nearest Neighbors in solid state, but with basis

    Homework Statement What is the area of the primitive cell for the lattice shown below? The nearest neighbor separation is "a." Homework Equations Here's the lattice we were given on our handout, and I have added the lines to indicate the square lattice (in red), the basis (in purple), and...
  4. W

    Linear chain with m th nearest neighbor interactions

    [b]1. Ashcroft and Mermin 22.1 Reexamine the theory of the linear chain without making the assumption that only nearest neighbors interact, using the harmonic potential energy of the form: U^harm=∑_n▒∑_(m>0)▒1/2 K_m [u(na)-u([n+m]a) ]^(1/2) Show that the dispersion relation must be...
  5. B

    MHB Book Recommendation for Nearest Neighbor Graphs

    Hello, I'm trying to read a paper titled "Cluster Identification in Nearest Neighbor Graphs". It's a mixture of probability, graph theory, and topology. I'm having difficulty interpreting some of the ideas, specially when it comes to k nearest neighbor graphs. I've been trying to look for a...
  6. P

    Help me, nearest neighbor problem.

    Hi everyone, I am new to computational geometry. As part of my master thesis, I have to solve a popular nearest neighbor problem. My task is to search for a point in a set of some 2000 4-dimensional points which is closest to a given point in the sense of Euclidean distance. After reading...
  7. U

    Nearest Neighbor lattice question

    Homework Statement An element crystalises in a face-centred cubic lattice with a basis group of two atoms at 000 and 1/4 1/4 1/4. The lattice constant is 3.55Angstroms. i) what is the separation of nearest neighbor atoms ii) how many nearest and second nearest neighbors does each atom...
  8. T

    Mean nearest neighbor distance in 3d

    Hi. In 3 dimensional Euclidean space with the usual metric, d=[(delta x)^2+(delta y)^2+(delta z)^2]^1/2, I'm trying to figure out the average distance between nearest neighbors in a randomly distributed sample of particles. My best initial guess for the average distance from any given particle...
  9. F

    Approximate finding nearest neighbor vectors

    Hello all. This problem is mostly math based, but is being applied to a programming algorithm. I'm working on a problem with a massive amount of normalized vectors in a massive amount of dimensions and need to quickly compute the nearest neighbors of anyone vector. More precisely, I need to...
  10. S

    Nearest neighbor and cheapest link algorithm

    Homework Statement I need to calculate the relative error of the nearest neighbor algorithm. The book says it is the difference between the worst and nearest neighbor solution to the nearest neighbor solution. Does the mean that for example I have CITY A, find the fastest way to back to city...
  11. S

    Spring-mass system with nearest neighbor couplings

    Hello, This problem refers particulary to the model in my attachment. The blocks are free to move but only along the x-axis. The springs connecting adjacent blocks have spring constant k1, while the two outer springs have stiffness k2. All the springs have a rest lengt of one. Write the matrix...