What is Nearest Neighbor Mapping?
Nearest neighbor mapping (NNS) is a search program that determines relationships between two unrelated datasets by quantifying their similarity (closeness). This type of map identifies the most similar (nearest) set of features in one dataset compared to a given starting point in another dataset.
This closeness is defined in terms of a “dissimilarity function.” Which means the less similar objects are, the larger the closeness function values are.
The nearest neighbor search can be defined as: “given a set S of points in a space M and a query point q ∈ M, find the closest point in S to q.”
Nearest Neighbor Mapping Techniques
While there are dozens of specific algorithms that each have their own dissimilarity functions, the most common NNS approaches are:
Exact matches:
Naïve Approach Search – This linear search technique finds the distance from the query point to every single point in the database, keeping a running “best so far” tally to deliver an exact match for the nearest neighbor.
K-D Tree Space partitioning – Continuously bisects the entire search space into ever smaller regions, each layer containing half the points from the last region.
Approximation:
Greedy search in proximity neighborhood graphs – Search begins from a starting vertex, continues by calculating the distances from the query point to each new vertex of the local neighborhood. Then finds and moves to the vertex with the minimal distance value, which becomes the new start point for the next search. Repeats until local minimum is found.
K-Nearest Neighbors – Adds feature weights fore every point that are stronger for more similar (closer) items. Then creates a graph that connects every point to its k-nearest neighbors based on those values.