COMPX270 — Randomised and Advanced Algorithms
Chapter 7: Nearest Neighbours & Dimensionality Reduction
High-dimensional nearest neighbour search: baseline approaches, approximate nearest neighbours, the Johnson–Lindenstrauss lemma for random projection, and locality-sensitive hashing for sub-linear query time.
Metric spaces, norms, random Gaussian vectors, concentration of χ² variables, and union bounds
The Nearest Neighbour Problem
Problem Definition
Given a dataset \(S\) of \(n\) points in a metric space \((X, \text{dist})\) with dimension \(d\), the Nearest Neighbour (NN) problem asks: given a query point \(x \in X\), find the point \(y \in S\) that minimises \(\text{dist}(x, y)\).
This is one of the most fundamental problems in computational geometry, machine learning, and data mining.
Definition: Metric Space
A metric space \((X, \text{dist})\) satisfies three axioms for all \(x, y, z \in X\):
- Reflexivity: \(\text{dist}(x, y) = 0 \iff x = y\)
- Symmetry: \(\text{dist}(x, y) = \text{dist}(y, x)\)
- Triangle Inequality: \(\text{dist}(x, z) \leq \text{dist}(x, y) + \text{dist}(y, z)\)
Common Distance Functions on \(\mathbb{R}^d\)
| Distance | Formula | Also Known As |
|---|---|---|
| Manhattan (\(\ell_1\)) | \(\|x - y\|_1 = \sum_{i=1}^{d} |x_i - y_i|\) | Taxicab distance |
| Euclidean (\(\ell_2\)) | \(\|x - y\|_2 = \sqrt{\sum_{i=1}^{d} (x_i - y_i)^2}\) | Straight-line distance |
| Hamming | \(\text{Ham}(x, y) = |\{i : x_i \neq y_i\}|\) | Bit-flip distance (for \(\{0,1\}^d\)) |
Baseline Approaches
Approach 1: Linear Scan (Linked List)
Store all \(n\) points in a list. For a query \(x\), scan all points and return the closest.
Approach 2: Bit Array (for \(\{0,1\}^d\))
Maintain a bit array \(A\) of size \(2^d\), where \(A[y] = 1\) iff \(y \in S\). For query \(x\), search by expanding Hamming balls of increasing radius.
Neither approach scales when both \(n\) and \(d\) are large. This motivates approximate methods.
Definition: Approximate Nearest Neighbour (ANN)
Given an approximation factor \(C > 1\), the \(C\)-ANN problem asks: given query \(x\), find \(y \in S\) such that
\[\text{dist}(x, y) \leq C \cdot \min_{y' \in S} \text{dist}(x, y')\]The Baby \(C\)-ANN variant assumes we know a target distance \(r\) and either: (a) returns a point within distance \(Cr\), or (b) certifies that no point is within distance \(r\).
Johnson–Lindenstrauss Lemma
The Curse of Dimensionality
Many algorithms for NN have runtime exponential in \(d\). The JL Lemma provides a powerful tool: random projection can reduce dimension from \(d\) to \(k = O(\log n / \varepsilon^2)\) while preserving all pairwise distances within a \((1 \pm \varepsilon)\) factor.
Random Projection
The projection map \(\Phi : \mathbb{R}^d \to \mathbb{R}^k\) is defined as:
\[\Phi(x) = Mx\]where \(M\) is a \(k \times d\) random matrix with entries drawn i.i.d. from \(\mathcal{N}(0, 1/k)\).
Theorem 36 (Distributional JL Lemma)
Let \(M\) be a \(k \times d\) matrix with entries i.i.d. \(\mathcal{N}(0, 1/k)\). For any fixed vector \(u \in \mathbb{R}^d\), any \(\varepsilon \in (0, 1)\), and any \(\delta > 0\), if
\[k = \Theta\!\left(\frac{\log(1/\delta)}{\varepsilon^2}\right)\]then:
\[\Pr\!\left[(1 - \varepsilon)\|u\|^2 \leq \|Mu\|^2 \leq (1 + \varepsilon)\|u\|^2\right] \geq 1 - \delta\]Write \(Mu = (Z_1, Z_2, \ldots, Z_k)\) where each \(Z_i = \langle m_i, u \rangle\) and \(m_i\) is the \(i\)-th row of \(M\). Each \(Z_i \sim \mathcal{N}(0, \|u\|^2/k)\), so \(kZ_i^2/\|u\|^2 \sim \chi^2(1)\).
Therefore \(\|Mu\|^2 = \sum_{i=1}^{k} Z_i^2\) and \(k\|Mu\|^2/\|u\|^2 \sim \chi^2(k)\). The expectation is \(\mathbb{E}[\|Mu\|^2] = \|u\|^2\). By sub-exponential concentration of \(\chi^2(k)\):
\[\Pr\!\left[\left|\frac{\|Mu\|^2}{\|u\|^2} - 1\right| > \varepsilon\right] \leq 2\exp\!\left(-\frac{k\varepsilon^2}{8}\right)\]Setting this \(\leq \delta\) and solving gives \(k = O(\log(1/\delta)/\varepsilon^2)\). \(\square\)
Corollary 36.1 (JL Lemma)
For any set \(S\) of \(n\) points in \(\mathbb{R}^d\) and any \(\varepsilon \in (0, 1)\), there exists a map \(\Phi : \mathbb{R}^d \to \mathbb{R}^k\) with
\[k = O\!\left(\frac{\log n}{\varepsilon^2}\right)\]such that for all pairs \(x, y \in S\):
\[(1 - \varepsilon)\|x - y\|^2 \leq \|\Phi(x) - \Phi(y)\|^2 \leq (1 + \varepsilon)\|x - y\|^2\]There are \(\binom{n}{2}\) pairs. Apply the Distributional JL Lemma to each difference vector \(u = x - y\) with failure probability \(\delta = 1/n^3\). By the union bound:
\[\Pr[\text{any pair fails}] \leq \binom{n}{2} \cdot \frac{1}{n^3} < \frac{1}{n}\]Setting \(k = \Theta(\log(n^3)/\varepsilon^2) = \Theta(\log n / \varepsilon^2)\) suffices. \(\square\)
Lemma 36.1: ANN via JL
Using random projection, we can solve the \((1+\varepsilon)\)-ANN problem with:
- Space: \(O(n \log n / \varepsilon^2)\)
- Query time: \(O(n \log n / \varepsilon^2)\)
This is still linear in \(n\) — we need LSH to achieve sub-linear query time.
Interactive: JL Dimensionality Reduction
Generate random points in high dimensions and project to lower dimensions. Observe how pairwise distances are preserved within the \((1 \pm \varepsilon)\) envelope.
Locality-Sensitive Hashing (LSH)
Motivation
The JL Lemma reduces dimension but still requires linear scan over all \(n\) points. LSH enables sub-linear query time by hashing points so that nearby points collide with high probability and far points collide with low probability.
Definition: LSH Family
A family \(\mathcal{H}\) of hash functions \(h : X \to U\) is \((r, Cr, p, q)\)-sensitive for a distance function \(\text{dist}\) if for all \(x, y \in X\):
- If \(\text{dist}(x, y) \leq r\) then \(\Pr_{h \sim \mathcal{H}}[h(x) = h(y)] \geq p\)
- If \(\text{dist}(x, y) \geq Cr\) then \(\Pr_{h \sim \mathcal{H}}[h(x) = h(y)] \leq q\)
We require \(p > q\) for the scheme to be useful.
Definition: Sensitivity Parameter \(\rho\)
The key quality measure of an LSH family is:
\[\rho = \frac{\log(1/p)}{\log(1/q)}\]We always have \(\rho < 1\) (since \(p > q\)). Smaller \(\rho\) means better separation between close and far points.
\(\ell\)-fold Amplification
Given an \((r, Cr, p, q)\)-sensitive family \(\mathcal{H}\), we can create a more powerful family by AND-composition: define \(g(x) = (h_1(x), h_2(x), \ldots, h_\ell(x))\) where each \(h_i\) is drawn independently from \(\mathcal{H}\). Then:
- Close points: collision prob \(\geq p^\ell\)
- Far points: collision prob \(\leq q^\ell\)
Lemma 36.2 (\(\ell\)-fold LSH Amplification)
The \(\ell\)-fold composition \(g = (h_1, \ldots, h_\ell)\) defines an \((r, Cr, p^\ell, q^\ell)\)-sensitive family. The sensitivity parameter remains:
\[\rho_\ell = \frac{\log(1/p^\ell)}{\log(1/q^\ell)} = \frac{\ell \log(1/p)}{\ell \log(1/q)} = \rho\]Theorem 37: LSH Data Structure
Given an \((r, Cr, p, q)\)-sensitive LSH family, we can build a data structure for Baby \(C\)-ANN with \(k\) hash tables, each using an \(\ell\)-fold LSH function composed with a regular hash function. Set \(\ell = \log_{1/p}(n)\) and \(k = n^{\rho}\).
Corollary 37.1: LSH Complexity
The LSH-based ANN data structure achieves:
- Space: \(O(n^{1+\rho} \cdot d)\)
- Query time: \(O(n^{\rho} \cdot d)\)
Since \(\rho < 1\), the query time is sub-linear in \(n\)!
Interactive: LSH Bucket Collision Visualization
See how random hyperplanes partition 2D space. Points close to the query (centre) are more likely to remain in the same hash bucket after multiple hashes (AND-amplification).
Collision Probability
LSH for Hamming Space
Bit Sampling LSH
For the Hamming space \(\{0, 1\}^d\), the simplest LSH family uses random coordinate projection:
\[h_i(x) = x_i \quad \text{(the } i\text{-th bit of } x\text{)}\]where \(i\) is chosen uniformly at random from \(\{1, 2, \ldots, d\}\).
Collision Probabilities
For \(x, y \in \{0,1\}^d\):
\[\Pr[h_i(x) = h_i(y)] = 1 - \frac{\text{Ham}(x, y)}{d}\]Therefore, if \(\text{Ham}(x, y) \leq r\) then \(p \geq 1 - r/d\), and if \(\text{Ham}(x, y) \geq Cr\) then \(q \leq 1 - Cr/d\).
Sensitivity Parameter for Hamming LSH
The sensitivity parameter is:
\[\rho = \frac{\log(1/p)}{\log(1/q)} = \frac{\log(1/(1 - r/d))}{\log(1/(1 - Cr/d))}\]For small \(r/d\), using \(\log(1/(1-x)) \approx x\):
\[\rho \approx \frac{r/d}{Cr/d} = \frac{1}{C}\]So Hamming LSH achieves \(\rho \approx 1/C\).
LSH for Euclidean Space (SimHash)
SimHash Construction
For Euclidean space \(\mathbb{R}^d\), the SimHash family uses random hyperplane projection:
\[h_g(x) = \text{sign}(\langle g, x \rangle)\]where \(g \sim \mathcal{N}(0, I_d)\) is a random Gaussian vector. The hash value is \(+1\) or \(-1\) depending on which side of the hyperplane \(g^{\perp}\) the point \(x\) falls.
Collision Probability
For any \(x, y \in \mathbb{R}^d\), the collision probability of SimHash is:
\[\Pr[h_g(x) = h_g(y)] = 1 - \frac{\alpha}{\pi}\]where \(\alpha = \arccos\!\left(\frac{\langle x, y \rangle}{\|x\| \cdot \|y\|}\right)\) is the angle between \(x\) and \(y\). Equivalently, for normalised vectors with \(\|x - y\| = r\):
\[\alpha = \arccos\!\left(1 - \frac{r^2}{2}\right)\]SimHash Sensitivity Parameter
For the \((r, Cr)\) setting with close points at distance \(r\) and far points at distance \(Cr\):
\[\rho = \frac{\log(1/p)}{\log(1/q)} = \frac{\log(1/(1 - \alpha_r/\pi))}{\log(1/(1 - \alpha_{Cr}/\pi))}\]where \(\alpha_r = \arccos(1 - r^2/2)\) and \(\alpha_{Cr} = \arccos(1 - C^2r^2/2)\).
One can show that \(\rho \leq 1/C\) for SimHash, matching the Hamming LSH bound.
Theorem 38: Baby ANN \(\to\) General ANN
If we have a data structure for Baby \(C\)-ANN with distance parameter \(r\), we can solve the general \(C\)-ANN problem via a doubling search over \(r\):
Try \(r = r_0, 2r_0, 4r_0, \ldots\) until we find a point. This introduces an extra \(O(\log \Delta)\) factor where \(\Delta\) is the aspect ratio (ratio of max to min pairwise distance).
- Space: \(O(n^{1+\rho} \cdot d \cdot \log \Delta)\)
- Query time: \(O(n^{\rho} \cdot d \cdot \log \Delta)\)
Summary & Comparison
| Method | Problem | Space | Query Time |
|---|---|---|---|
| Linear Scan | Exact NN | \(O(nd)\) | \(O(nd)\) |
| Bit Array | Exact NN (Hamming) | \(O(2^d)\) | \(O(2^d)\) |
| JL Projection | \((1+\varepsilon)\)-ANN | \(O(n \log n / \varepsilon^2)\) | \(O(n \log n / \varepsilon^2)\) |
| Hamming LSH | \(C\)-ANN | \(O(n^{1+1/C} d)\) | \(O(n^{1/C} d)\) |
| SimHash (Euclidean) | \(C\)-ANN | \(O(n^{1+1/C} d)\) | \(O(n^{1/C} d)\) |
Key Takeaways
- The NN problem in high dimensions suffers from the curse of dimensionality: exact methods require time/space exponential in \(d\).
- The JL Lemma shows that \(O(\log n / \varepsilon^2)\) dimensions suffice to preserve all pairwise distances — but query time is still \(O(n)\).
- LSH achieves sub-linear query time \(O(n^{\rho} d)\) with \(\rho < 1\), by hashing points so that nearby points are more likely to collide.
- For Hamming and Euclidean spaces, \(\rho \approx 1/C\) where \(C\) is the approximation factor.
- Baby ANN can be lifted to General ANN via doubling search at an extra \(O(\log \Delta)\) cost.
Tutorial Problems
Work through these problems to deepen your understanding of nearest neighbours and dimensionality reduction.
Problem 1 Warm-up
Describe a baseline data structure for the NN problem that stores \(n\) points from \(\{0,1\}^d\) in a linked list. Analyse its space and query time.
Store each of the \(n\) points as a node in a linked list, where each node contains a \(d\)-bit string.
- Space: \(O(nd)\) — each of \(n\) points takes \(d\) bits.
- Insert: \(O(d)\) — append a new node with the \(d\)-bit string.
- Query: \(O(nd)\) — scan all \(n\) points, computing \(\text{Ham}(x, y)\) in \(O(d)\) time for each, and return the closest.
\(\square\)
Problem 2 Warm-up
Describe a bit-array approach for NN in \(\{0,1\}^d\). What are the space and insert-time complexities? Why is query time \(O(2^d)\) in the worst case?
Maintain an array \(A[0 \ldots 2^d - 1]\) indexed by all possible \(d\)-bit strings, where \(A[y] = 1\) iff \(y \in S\).
- Space: \(O(2^d)\) bits.
- Insert: \(O(1)\) — just set \(A[y] = 1\).
- Query: For query \(x\), enumerate all \(y \in \{0,1\}^d\) at Hamming distance 0, then 1, then 2, etc., checking \(A[y]\). In the worst case (no nearby points), we must check all \(2^d\) entries: \(O(2^d)\) time.
\(\square\)
Problem 3 Warm-up
Explain why Bloom filters cannot directly solve the ANN problem. What fundamental limitation do they have?
A Bloom filter supports membership testing: given \(y\), it can (approximately) answer “is \(y \in S\)?” However, it cannot return an actual element of \(S\). For ANN, we need to return a specific point \(y \in S\) that is close to the query \(x\). The Bloom filter only answers yes/no for each candidate point, and:
- It cannot enumerate the elements of \(S\).
- It has false positives (may say “yes” for \(y \notin S\)).
- Even if we iterate over Hamming balls, false positives mean we might return a non-existent point.
LSH hash tables, unlike Bloom filters, store actual data points in buckets, allowing retrieval. \(\square\)
Problem 4 Problem Solving ⭐
Show how to reduce Baby \(C\)-ANN (with known distance threshold \(r\)) to General \(C\)-ANN using a doubling search. What is the overhead?
Doubling search: Let \(\Delta = \max/\min\) pairwise distance (the aspect ratio). Build Baby \(C\)-ANN data structures for each distance scale \(r = r_{\min}, 2r_{\min}, 4r_{\min}, \ldots, r_{\max}\). There are \(O(\log \Delta)\) scales.
On a query \(x\):
- For each scale \(r\) (starting from smallest), query the Baby ANN structure.
- If the structure returns a point \(y\) within distance \(Cr\), return \(y\).
- If it certifies no point is within distance \(r\), try the next larger scale.
Correctness: If the true nearest neighbour is at distance \(r^*\), then for the scale \(r\) with \(r \leq r^* \leq 2r\), the Baby ANN must return a point within distance \(Cr \leq 2Cr^*\). With more care, one gets \(C\)-ANN.
Overhead: Space and query time are multiplied by \(O(\log \Delta)\). \(\square\)
Problem 5 Problem Solving ⭐
For SimHash on unit vectors, show that the collision probability is \(1 - \alpha/\pi\) where \(\alpha = \arccos(1 - r^2/2)\). Then show that \(\rho \leq 1/C\) for the \((r, Cr)\) setting.
Collision probability: Two unit vectors \(x, y\) with angle \(\alpha\) between them have \(h_g(x) = h_g(y)\) iff the random hyperplane \(g^{\perp}\) does not separate them. The probability that a random hyperplane separates two vectors at angle \(\alpha\) is \(\alpha/\pi\). So:
\[\Pr[h_g(x) = h_g(y)] = 1 - \frac{\alpha}{\pi}\]For unit vectors \(\|x\| = \|y\| = 1\) with \(\|x - y\| = r\):
\[\|x - y\|^2 = 2 - 2\langle x, y \rangle = r^2 \implies \langle x, y \rangle = 1 - r^2/2\]So \(\alpha = \arccos(1 - r^2/2)\).
Showing \(\rho \leq 1/C\): For close points (\(\text{dist} = r\)), \(p = 1 - \alpha_r/\pi\). For far points (\(\text{dist} = Cr\)), \(q = 1 - \alpha_{Cr}/\pi\). Since \(\alpha_{Cr} \geq C \cdot \alpha_r\) (by concavity of arccos in the relevant range), we get \(\rho = \log(1/p)/\log(1/q) \leq 1/C\). \(\square\)
Problem 6 Problem Solving ⭐
Define the Jaccard distance between two sets \(A, B \subseteq [n]\) as \(\text{dist}_J(A, B) = 1 - |A \cap B|/|A \cup B|\). Describe the MinHash LSH family for Jaccard distance and explain why it works.
Jaccard similarity: \(J(A, B) = |A \cap B| / |A \cup B|\), so \(\text{dist}_J(A, B) = 1 - J(A, B)\).
MinHash family: Let \(\sigma\) be a uniformly random permutation of \([n]\). Define:
\[h_\sigma(A) = \min_{a \in A} \sigma(a)\]The family \(\mathcal{H}\) consists of all \(n!\) such functions (one per permutation).
Collision probability:
\[\Pr[h_\sigma(A) = h_\sigma(B)] = \frac{|A \cap B|}{|A \cup B|} = J(A, B)\]This holds because the minimum of a random permutation over \(A \cup B\) lands in \(A \cap B\) with probability \(|A \cap B|/|A \cup B|\).
For \((r, Cr)\)-sensitivity: \(p = 1 - r\) (close sets), \(q = 1 - Cr\) (far sets). The sensitivity parameter is \(\rho = \log(1/(1-r))/\log(1/(1-Cr))\). \(\square\)
Problem 7 Advanced ⭐⭐
Describe the kd-tree data structure for Euclidean NN. Explain how it partitions space and why its query time degrades in high dimensions.
kd-tree construction: A kd-tree is a binary space-partitioning tree that recursively divides \(\mathbb{R}^d\):
- At each level, choose a coordinate (cycling through dimensions 1 to \(d\)).
- Split on the median value along that coordinate.
- Points below the median go to the left subtree; above to the right.
Query algorithm: For query \(x\), traverse the tree to find the leaf cell containing \(x\). Then backtrack, pruning subtrees whose bounding boxes are farther than the current best distance.
Complexity:
- Space: \(O(nd)\) — each point is stored once.
- Low dimensions (\(d\) small): Expected \(O(\log n)\) query time on well-distributed data.
- High dimensions: The pruning becomes ineffective because bounding boxes overlap heavily. Worst case degrades to \(O(n^{1 - 1/d} + k)\), which approaches \(O(n)\) as \(d\) grows.
This is why kd-trees are not suitable for high-dimensional NN, motivating the JL and LSH approaches. \(\square\)
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).