k-Nearest Neighbors

Background

Proposed by Fix and Hodges in 1951, one of the oldest non-parametric classifiers
No training phase - all computation happens at prediction time
Universally consistent: as data grows, error approaches Bayes-optimal

The Concept

K-nearest neighbors classifies a new point by finding the k most similar training examples and taking a majority vote among their labels (or averaging for regression). No model parameters are learned - the training data IS the model.

How it Links

Motivates why distance metrics and feature scaling matter enormously
The curse of dimensionality is most viscerally understood via kNN degradation in high dimensions
Connects to locality-sensitive hashing and approximate nearest-neighbor search in production systems

Concrete Example

Recommending a movie: find the 10 most similar users (nearest neighbors by watch history) and recommend what they liked that you have not seen yet. This is collaborative filtering - kNN applied to user-item embeddings.

Prerequisites

Math you need: linear algebra and probability, Bias, variance, over/under-fitting, Evaluation metrics

Learning outcomes

State the k-NN classification and regression rules and the role of the distance metric.
Recognize the curse of dimensionality via the concentration-of-distances argument.
Reproduce the Cover-Hart bound R_1NN <= 2 R*(1 - R*) and explain its consequences.
Explain when KD-trees, ball trees, and HNSW each pay off, and when none of them do.
Implement brute-force k-NN in NumPy and call it through sklearn or FAISS at scale.

TL;DR

k-NN is a non-parametric classifier: given a query $x$ , find the $k$ training points closest under a chosen metric and take their majority vote (classification) or mean (regression). It has zero training cost and $O(n d)$ inference, so it is the textbook lazy learner. Cover and Hart proved that the asymptotic 1-NN error is at most twice the Bayes error [2]. The whole approach breaks under the curse of dimensionality - distances concentrate, and “nearest” loses meaning - which is why production systems use approximate methods like LSH [3], HNSW [4], and FAISS for large-scale retrieval.

Intuition

The k-NN rule is the simplest learning algorithm that works. To classify a new point, look at its $k$ closest training neighbours and vote. To regress, average their targets. There is no model to fit, no parameters to optimize: the training set is the model. That makes k-NN powerful (it can represent any decision boundary if you have enough data) and brittle (every prediction touches the entire training set, and it falls apart in high dimensions).

Three knobs control the behaviour:

The distance metric $d(x, x')$ . Euclidean is the default, but Manhattan, cosine, and Mahalanobis are all useful when the geometry matches the data.
The number of neighbours $k$ . Small $k$ has low bias and high variance (jagged boundary); large $k$ smooths the boundary and adds bias. Choose $k$ by cross-validation.
The vote weighting. Uniform votes treat all $k$ neighbours equally; inverse-distance and Gaussian-kernel weights down-weight far-away neighbours.

What kNN really learns

k-NN does not learn a model of the data; it memorizes the training set and defers all work to query time. Its decision boundary at any test point is the locally majority-voted class within the $k$ -th nearest ball, which is a piecewise constant function of $x$ . As $k$ grows, the boundary smooths; as $n$ grows, it converges to the Bayes-optimal boundary almost everywhere. This is why k-NN is consistent - it eventually gets every example right, given enough data [1].

Distance metrics

Metric	Formula	When it fits
Euclidean (L2)	sqrt(sum_i (x_i - y_i)^2)	Continuous features on comparable scales; the default.
Manhattan (L1)	sum_i \|x_i - y_i\|	Robust to a few large per-feature deviations; grids, taxicab geometry.
Mahalanobis	sqrt((x - y)^T Sigma^{-1} (x - y))	Correlated or differently-scaled features; whitens the input space using the inverse covariance.
Cosine	1 - (x . y) / (\|\|x\|\| \|\|y\|\|)	High-dimensional sparse vectors (text, embeddings) where direction matters more than magnitude.
Hamming	count of positions where x_i != y_i	Categorical or binary features.

The Mahalanobis metric is worth pausing on. With $\Sigma = \operatorname{Cov}(X)$ , distance $\sqrt{(x - y)^{\top}\Sigma^{-1}(x - y)}$ is the Euclidean distance after whitening the data with $\Sigma^{-1/2}$ . Equivalently, you map each axis to its z-score and decorrelate. This is the right metric whenever your features are on different scales or correlated - e.g. height-and-weight pairs - and it is the unique linear distance that makes “one standard deviation” mean the same thing along every direction.

Math

Curse of dimensionality: distances concentrate

A surprising fact about high-dimensional metric spaces: pairwise distances concentrate around a common value, so “nearest” stops carrying information. Concretely, suppose $X_1, \dots, X_n$ are i.i.d. samples in $\mathbb{R}^{d}$ with i.i.d. coordinates of finite variance. For a fixed query $q$ , define

D_{\min}(d) = \min_{i}\,\lVert X_i - q \rVert_{2}, \qquad D_{\max}(d) = \max_{i}\,\lVert X_i - q \rVert_{2}.

Beyer, Goldstein, Ramakrishnan, and Shaft (1999) showed that under mild moment conditions on the coordinate distribution,

\frac{D_{\max}(d) - D_{\min}(d)}{D_{\min}(d)} \xrightarrow{p} 0 \quad \text{as } d \to \infty.

That is, the contrast ratio between the farthest and the nearest training point shrinks towards zero. In high dimensions everything is roughly equidistant from your query, and any nearest-neighbour query is essentially picking a random point.

A back-of-the-envelope reason: if each coordinate contributes independent noise of variance $\sigma^{2}$ , then $\lVert X - q \rVert_{2}^{2}$ is a sum of $d$ i.i.d. terms with mean $\mu d$ and variance $\Theta(d)$ . By the central limit theorem, $\lVert X - q \rVert_{2} \approx \sqrt{\mu d}\,\bigl(1 + O(d^{-1/2})\bigr)$ , so distances cluster around $\sqrt{\mu d}$ with relative width $O(d^{-1/2})$ . Doubling $d$ shrinks the relative gap between nearest and farthest by a factor of $\sqrt{2}$ .

The practical consequence: brute-force k-NN on raw, very-high-dimensional features (e.g. 4096-dim image embeddings) returns a “nearest neighbour” whose distance is barely smaller than the median distance - the lookup carries little signal. The fix is one of: dimensionality reduction (PCA, autoencoder), a learned distance (metric learning), or an approximate method that admits the loss of contrast and uses fewer probes [1][3].

The Cover-Hart 1-NN bound

Statement

Let $R^{\star}$ be the Bayes error rate - the minimum achievable error of any classifier - and let $R_{\mathrm{1NN}}$ be the asymptotic ( $n \to \infty$ ) error rate of the 1-nearest-neighbour rule. Then for two-class problems,

R^{\star} \le R_{\mathrm{1NN}} \le 2\,R^{\star}\,(1 - R^{\star}) \le 2\,R^{\star}.

In words: in the limit of infinite data, 1-NN’s error is at most twice the Bayes error. For multi-class problems with $K$ classes the bound generalizes to $R_{\mathrm{1NN}} \le R^{\star}\,(2 - \tfrac{K}{K-1}\,R^{\star})$ [2].

Proof sketch (two-class case)

Fix a query $x$ and let $\eta(x) = P(y = 1 \mid x)$ . The Bayes-optimal rule predicts $\hat{y}_{\mathrm{B}}(x) = \mathbb{1}[\eta(x) \ge 1/2]$ with conditional error

r^{\star}(x) = \min\bigl(\eta(x),\ 1 - \eta(x)\bigr).

Now consider 1-NN. Let $X'$ be the nearest training point to $x$ and $y'$ its label. As $n \to \infty$ , almost-sure convergence of $X'$ to $x$ implies $\eta(X') \to \eta(x)$ . The 1-NN classifier predicts $y'$ . Conditional on $x$ and $X'$ , $y'$ is Bernoulli $\,\bigl(\eta(X')\bigr)$ and the true label $y$ is independently Bernoulli $\,\bigl(\eta(x)\bigr)$ . So 1-NN errs iff $y \ne y'$ :

r_{\mathrm{1NN}}(x) = \eta(x)\,(1 - \eta(X')) + (1 - \eta(x))\,\eta(X').

Taking the limit $\eta(X') \to \eta(x)$ ,

r_{\mathrm{1NN}}(x) \to 2\,\eta(x)\,(1 - \eta(x)).

Use $\eta(1 - \eta) = (1 - r^{\star})\,r^{\star}$ when $r^{\star} = \min(\eta, 1 - \eta)$ to get

r_{\mathrm{1NN}}(x) \to 2\,r^{\star}(x)\,\bigl(1 - r^{\star}(x)\bigr).

Take expectations over $x$ and apply Jensen’s inequality (the function $r \mapsto 2 r (1 - r)$ is concave) to obtain $R_{\mathrm{1NN}} \le 2\,R^{\star}\,(1 - R^{\star}) \le 2\,R^{\star}$ . The lower bound $R_{\mathrm{1NN}} \ge R^{\star}$ holds because no classifier beats the Bayes rule. ∎

The bound is tight in the following sense. The first inequality $R_{\mathrm{1NN}} \le 2\,R^{\star}\,(1 - R^{\star})$ is achieved with equality whenever $r^{\star}(x) = \min(\eta(x), 1 - \eta(x))$ is a.s. constant on the support of the input distribution, because Jensen’s inequality holds with equality on a constant. Equivalently, the condition is that $\eta(x) \in \{c, 1 - c\}$ a.s. for some $c \in [0, 1/2]$ . The second inequality $2\,R^{\star}\,(1 - R^{\star}) \le 2\,R^{\star}$ becomes tight as $R^{\star} \to 0$ . In practice 1-NN often does better than $2\,R^{\star}$ but never asymptotically worse.

Why $k > 1$ helps

For $k > 1$ neighbours with $k \to \infty$ and $k/n \to 0$ , the k-NN rule is Bayes-consistent: $R_{k\mathrm{NN}} \to R^{\star}$ . The intuition is that $k$ neighbours are an empirical estimate of $\eta(x)$ in a shrinking ball around $x$ , and a majority vote over $k$ Bernoulli trials of mean $\eta$ converges to $\mathbb{1}[\eta \ge 1/2]$ as $k \to \infty$ . So at infinite $n$ , $k$ -NN with the right rate of $k$ is as good as the Bayes rule, while 1-NN pays a factor-of-2 surcharge for being maximally noisy [2][1].

Choosing k

There is no formula for $k$ . The standard recipe:

Hold out a validation set, or use $K$ -fold cross-validation.
Try a grid of $k \in \{1, 3, 5, 7, 11, 21, 51, \dots\}$ - odd values for binary classification to avoid ties.
Pick the $k$ that minimizes validation error (or maximizes whatever objective you care about: accuracy, AUC, log-loss).

A useful sanity check is the bias-variance picture: $k = 1$ is high-variance, low-bias; $k = n$ predicts the global majority class with low variance and maximum bias. The sweet spot trades these off.

Weighted kNN

Instead of a uniform vote, weight neighbour $i$ by $w_i = 1 / d(x, x_i)$ (inverse distance) or by a Gaussian kernel $w_i = \exp(-d(x, x_i)^{2} / 2\sigma^{2})$ . This is the bridge from k-NN to kernel density estimation and Nadaraya-Watson regression [1]: as $\sigma \to 0$ you recover hard k-NN; as $\sigma \to \infty$ you recover global mean. With weights, ties are rarer and the boundary is smoother.

Fast lookup at scale

Method	Build cost	Query cost	Exact?	Best dimensionality	Notes
Brute force	O(n d) (just store the data)	O(n d) per query	yes	any	The reference. Always correct, hopeless past a few million points.
KD-tree	O(n d log n)	O(log n) average; O(n) worst case	yes	low (d < ~20)	Splits axes one at a time. Degrades sharply once d grows because the bounding boxes overlap most of space.
Ball tree	O(n d log n)	O(log n) average; O(n) worst case	yes	low to mid (d < ~30)	Hyperspheres instead of axis-aligned boxes. Better for non-axis-aligned clusters than KD-trees, still beaten in high d.
LSH (Indyk-Motwani)	O(n L k_h)	O(L) hash lookups + O(L) candidates per query	no (probabilistic)	mid to high	Hash colliding points to the same bucket with high probability. Trades off accuracy for speed via L hash tables.
HNSW	O(n log n)	O(log n) hops on a navigable small-world graph	no (high recall)	mid to high	State-of-the-art ANN graph. Very high recall at sub-linear query cost.
IVF / FAISS / ScaNN	O(n)	O(n / nlist + nprobe)	no	mid to high	Inverted lists from k-means coarse quantization, often combined with PQ for memory.

KD-trees fail in high d

KD-trees and ball trees are exact and wonderful in low dimensions. Past about $d = 20$ , the bounding regions of sibling nodes overlap so heavily that the tree barely prunes the search and the algorithm degenerates to brute force. The empirical rule of thumb in sklearn is to switch to brute force above $d \approx 30$ . For high-dimensional embeddings, use approximate methods (LSH, HNSW, FAISS) or reduce dimensionality first.

Algorithm

# Brute-force k-NN classification (pseudocode)
def knn_predict(X_train, y_train, X_query, k=5):
    preds = []
    for q in X_query:
        # 1) compute distances to every training point
        d = euclidean(X_train, q)                   # shape (n,)
        # 2) take the k smallest
        idx = argpartition(d, k)[:k]
        # 3) majority vote over their labels
        preds.append(majority(y_train[idx]))
    return preds
 
# Weighted variant: replace majority(...) with argmax over class-weighted sums.

Implementations

python

import numpy as np
from collections import Counter

def knn_predict(X_train, y_train, X_query, k=5):
  """Brute-force k-NN classification with Euclidean distance."""
  # squared distances via the (a-b)^2 = a^2 - 2 a.b + b^2 trick (vectorized)
  train_sq = (X_train ** 2).sum(axis=1)           # (n,)
  query_sq = (X_query ** 2).sum(axis=1)           # (m,)
  cross    = X_query @ X_train.T                  # (m, n)
  d2 = query_sq[:, None] - 2 * cross + train_sq[None, :]   # (m, n)
  nn = np.argpartition(d2, kth=k - 1, axis=1)[:, :k]       # (m, k) indices
  preds = []
  for row in nn:
      vote = Counter(y_train[row]).most_common(1)[0][0]
      preds.append(vote)
  return np.array(preds)

# tiny synthetic 2D dataset with two overlapping classes
rng = np.random.default_rng(0)
X_pos = rng.normal(loc=[+1, +1], scale=0.7, size=(60, 2))
X_neg = rng.normal(loc=[-1, -1], scale=0.7, size=(60, 2))
X = np.vstack([X_pos, X_neg]); y = np.array([1] * 60 + [0] * 60)

# 80/20 split
perm = rng.permutation(len(y))
X, y = X[perm], y[perm]
n_tr = int(0.8 * len(y))
X_tr, y_tr = X[:n_tr], y[:n_tr]
X_te, y_te = X[n_tr:], y[n_tr:]

for k in (1, 3, 5, 10):
  yhat = knn_predict(X_tr, y_tr, X_te, k=k)
  acc = float((yhat == y_te).mean())
  print(f"k={k:2d}  test accuracy = {acc:.3f}")

The (a - b)^2 expansion is the standard trick for batched Euclidean distances. argpartition is O(n) per query, faster than sort.

Run the from-scratch NumPy brute-force kNN live in the browser:

Idle (packages: numpy)

(no output yet)

How it compares to nearby classifiers

Method	Training cost	Inference cost	Parametric?	Non-linear boundary?	Interpretable?	Notes
k-NN	O(1) (just store data)	O(n d) per query, brute force	no (lazy learner)	yes (any boundary in the limit)	low (no learned weights)	Memory-bound. Use ANN at scale.
Logistic regression	O(n d) per IRLS iter	O(d) per query	yes	no (linear boundary in feature space)	high (per-feature coefficients)	Fast inference; needs feature engineering for non-linear boundaries.
Decision tree	O(n d log n)	O(depth)	no (non-parametric in depth)	yes (axis-aligned)	high (path-as-rule)	No distance metric needed; handles mixed types naturally.

Real-world uses

Domain	System	Why nearest neighbour
Image / video retrieval	Reverse-image search, content-id, fingerprinting	Embed once, then nearest-neighbour over the embedding space; FAISS / ScaNN handles billions of vectors.
Recommender systems	Two-tower candidate generation	Embed users and items; ANN over item embeddings with the user embedding as query produces the candidate set in O(log n).
Anomaly detection	kNN-distance score (LOF, kNN-graph)	Points whose k-th nearest neighbour distance is unusually large are flagged as outliers.
Computer vision	k-NN on deep features (e.g. perceptual loss, retrieval baselines)	Cheap baseline that surprisingly often matches a fine-tuned classifier on out-of-distribution settings.
NLP	kNN-LM, kNN-MT (retrieval-augmented language models)	A large embedded datastore is queried at inference to inject memorized examples into the model output.

Pitfalls

Distances explode in raw high-dim space

Brute-force k-NN on raw, very-high-dimensional features fails to discriminate because the contrast ratio between far and near collapses. Either reduce dimensionality (PCA, UMAP, an autoencoder), learn a metric, or switch to ANN methods that admit the loss of contrast.

k-NN inherits the scale of your features

A feature in metres dominates a feature in millimetres by a factor of a million in squared Euclidean distance. Always standardize (zero mean, unit variance) or use Mahalanobis to put features on a comparable footing.

Memory and latency at inference

There is no model to ship - the whole training set has to live somewhere. For 1M 1024-dim float32 vectors that is 4 GB. Production deployments use quantization (PQ, OPQ), inverted-file indices (IVF), or hierarchical graphs (HNSW) to fit and query within latency budgets.

Use kNN as a sanity check, then move on

It is the textbook baseline classifier. Run it on your problem first - if a parametric model cannot beat well-tuned k-NN, the parametric model is broken or the features are wrong, not the other way round.

Interview Q&A

Sketch the proof of the Cover-Hart 1-NN bound and state the result.research

Statement. As $n \to \infty$ , the asymptotic error of the 1-nearest-neighbour rule is

R^{\star} \le R_{\mathrm{1NN}} \le 2\,R^{\star}\,(1 - R^{\star}) \le 2\,R^{\star},

where $R^{\star}$ is the Bayes error rate [2].

Sketch. Fix a query $x$ with $\eta(x) = P(y = 1 \mid x)$ , and let $X'$ be its 1-NN with label $y'$ . Bayes-optimal conditional error is $r^{\star}(x) = \min(\eta(x), 1 - \eta(x))$ . As $n \to \infty$ , $X' \to x$ almost surely, so $\eta(X') \to \eta(x)$ . Conditional on $x$ and $X'$ , the true label $y$ and the neighbour label $y'$ are independent Bernoullis with parameters $\eta(x)$ and $\eta(X')$ , so

r_{\mathrm{1NN}}(x) = \eta(x)(1 - \eta(X')) + (1 - \eta(x))\,\eta(X') \to 2\,\eta(x)\,(1 - \eta(x)).

Using $\eta(1 - \eta) = r^{\star}(1 - r^{\star})$ , $r_{\mathrm{1NN}}(x) \to 2\,r^{\star}(x)(1 - r^{\star}(x))$ . Take expectations over $x$ and apply Jensen (the function is concave) to get $R_{\mathrm{1NN}} \le 2\,R^{\star}\,(1 - R^{\star}) \le 2\,R^{\star}$ . The lower bound is trivial because no rule beats Bayes. ∎

The bound is tight when $\eta$ takes only the values $0, 1/2, 1$ . Note that no other classifier with infinite data is guaranteed to be within $2 R^{\star}$ without further assumptions; that is what makes 1-NN special.

What changes for k-NN with k > 1, and why is k-NN consistent?research

For $k > 1$ neighbours, the k-NN rule predicts the majority label among the $k$ closest training points. The crucial result is Bayes consistency: if $k = k_n$ satisfies $k_n \to \infty$ and $k_n / n \to 0$ , then $R_{k\mathrm{NN}} \to R^{\star}$ as $n \to \infty$ .

Heuristically, the $k$ nearest neighbours give an empirical estimate of $\eta(x)$ in a shrinking ball around $x$ . As $n \to \infty$ with the right $k_n$ schedule, the ball shrinks (so the bias from $\eta$ varying inside the ball vanishes), but $k_n$ grows (so the variance of the empirical proportion of class 1 vanishes). A majority vote on $k_n$ Bernoulli $(\eta(x))$ trials converges to $\mathbb{1}[\eta(x) \ge 1/2]$ , which is the Bayes rule. So with a properly chosen schedule, k-NN matches the Bayes error in the limit.

In practice $k$ is chosen by cross-validation: small $k$ has low bias and high variance; large $k$ smooths but introduces bias by averaging far-away neighbours [1].

Why does the curse of dimensionality break k-NN, and what does the concentration-of-distances argument actually show?onsite

In high dimensions, pairwise distances concentrate around a common value, so the contrast between the nearest and farthest training points to a query collapses. Formally, for i.i.d. coordinates of finite variance,

\frac{D_{\max}(d) - D_{\min}(d)}{D_{\min}(d)} \xrightarrow{p} 0 \quad \text{as } d \to \infty.

The intuition: $\lVert X - q \rVert_{2}^{2}$ is a sum of $d$ i.i.d. terms, with mean $\propto d$ and variance $\propto d$ , so the relative fluctuation is $O(d^{-1/2})$ . Doubling $d$ shrinks the gap between near and far by $\sqrt{2}$ .

For k-NN this means: in raw 4096-dimensional embeddings, the “nearest neighbour” is barely closer than the median training point - the discriminative signal in the lookup is gone. The fixes in practice:

Reduce dimensionality (PCA, UMAP, an autoencoder, or a learned projection).
Learn a metric (large-margin nearest neighbour, triplet losses), so distances reflect class structure rather than raw geometry.
Switch to approximate methods (LSH, HNSW) that explicitly trade a bit of recall for orders-of-magnitude speed-ups, since exact lookup is buying you very little anyway in this regime [3][4].

Compare KD-tree, ball tree, and HNSW. When does each pay off?onsite

KD-tree. Recursively splits the training set on one axis at a time at the median. Build $O(n d \log n)$ , query $O(\log n)$ on average for low $d$ . Beautiful in $d \le 20$ ; degrades to $O(n)$ once the bounding boxes of sibling nodes overlap most of space, which happens fast as $d$ grows. Exact.

Ball tree. Same recursive partitioning, but with hyperspherical bounding regions instead of axis-aligned boxes. Handles non-axis-aligned data better than KD-tree (e.g. correlated features), but suffers from the same dimensionality issue around $d \approx 30$ . Exact.

HNSW (Hierarchical Navigable Small World graph). Builds a multi-layer proximity graph: top layers have few well-connected nodes for long-range hops, bottom layers densely connect every node to its near neighbours [4]. Search starts at the top, greedily descends. Build $O(n \log n)$ , query $O(\log n)$ with very high recall in mid-to-high dimensions. Approximate, with a knob (efSearch) trading recall for latency.

Rules of thumb.

$d \lesssim 20$ : KD-tree on raw data is fastest and exact.
$d \approx 20\!-\!30$ : ball tree if data is non-axis-aligned, otherwise brute force.
$d \gtrsim 30$ and $n \gtrsim 10^{5}$ : HNSW or IVF-PQ in FAISS / ScaNN, after you have reduced dimensionality if possible.
$n \lesssim 10^{4}$ at any $d$ : just brute-force; cache locality wins.

Check yourself

Score: 0 / 5(0 answered)

1. What does k-NN do at training time?
2. What is the asymptotic Cover-Hart bound on the 1-NN error rate (binary case)?
3. Why does brute-force k-NN fail in very high dimensions even with large n?
4. In sklearn, why does the documentation switch from KD-tree / ball tree to brute force around d ~ 30?
5. Which production scenario does HNSW especially target?

Build it yourself

A short evening project:

Take MNIST. Implement brute-force k-NN with Euclidean distance and report test accuracy across $k \in \{1, 3, 5, 11, 21\}$ .
Add inverse-distance weighting and re-run; you should see a small improvement.
Replace raw pixels with a 64-dim PCA projection and confirm accuracy improves and queries run faster.
Switch to sklearn.neighbors.NearestNeighbors(algorithm='ball_tree') and confirm exact agreement with brute force, then time the difference.
Stretch: index the same projected vectors in faiss.IndexHNSWFlat(d=64, M=32), sweep efSearch, and plot the recall@10 vs query-latency curve.

Interactive Demo

k-NN Decision Region Demo

k = 3

Add as:Class AClass B

Class A (red): 10

Class B (blue): 10

Total: 20

What to try: Add points near the boundary and change k to see how the decision region smooths as k increases. Hover a point to see its k nearest neighbors.

References

Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed.. Springer. https://hastie.su.domains/ElemStatLearn/
Cover, T. M. and Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory 13(1), 21-27. doi:10.1109/TIT.1967.1053964
Indyk, P. and Motwani, R. (1998). Approximate nearest neighbors: towards removing the curse of dimensionality. Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), 604-613. doi:10.1145/276698.276876
Malkov, Y. A. and Yashunin, D. A. (2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence. arXiv:1603.09320

Logistic Regression Decision Trees