Nearest Neighbour

From Algorithm Wiki
Revision as of 12:14, 21 September 2021 by Yashsherry (talk | contribs) (→‎Problem Description)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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

NNSStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
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)]

logn