Nearest Neighbour

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

K Nearest Neighbour is a simple algorithm that stores all the available cases and classifies the new data or case based on a similarity measure. It is mostly used to classifies a data point based on how its neighbours are classified.

Bounds Chart

Nearest Neighbor SearchBoundsChart.png

Step Chart


Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Polynomial > 3
Quadratic [Linear search (1940)]
nlogn k-d Tree (1975)

R tree (1984)

HNSW (2016)

Locality sensitive hashing (2010)

Linear Projected radial search (2013)

[Compression/Clustering Vector Quantization (1992)]