UUtah Fall 2026 | Data Mining | L5 NN Search

Overview

Nearest-neighbor search turns a distance function into a scalable retrieval system by preprocessing data and answering queries without scanning every point. The lecture progresses from exact one-dimensional trees and two-dimensional Voronoi diagrams to approximate KD-trees, locality-sensitive hashing, and Hierarchical Navigable Small World (HNSW) graphs, explaining why HNSW-style vector search works well in high-dimensional practice despite the curse of dimensionality.

Key takeaways

A balanced binary tree over sorted one-dimensional data supports exact nearest-neighbor queries in O(log N) time with O(N) storage, after O(N log N) preprocessing.
Exact Voronoi-based search scales poorly beyond two dimensions: its space can grow as N^ceil(D/2), reaching quadratic size at D = 3.
Approximate search permits a returned point up to 1 + ε times the true nearest-neighbor distance; this relaxation enables pruning and randomized indexing methods.
Locality-sensitive hashing offers dimension-insensitive approximate-search bounds aside from reading coordinates, but HNSW has proved more effective in many practical high-dimensional benchmarks.
HNSW combines sparse, randomly promoted graph layers with beam search, using long-range navigation above and multiple candidate paths to reduce local-minimum failures.
Vector databases make approximate nearest-neighbor retrieval practical for embedding workloads, including Euclidean and cosine similarity search.

Chapters

0:00 Implementation Efficiency and the Nearest-Neighbor Search Roadmap

The first homework is due at the end of the day; implementation choices can greatly change runtime even when scalability trials are completed.
Nearest-neighbor search is introduced as a scalability problem: preprocess a dataset once, then retrieve close points efficiently.
The lecture roadmap leads from basic data structures to modern Hierarchical Navigable Small World graphs.

3:20 Rich Sutton’s Bitter Lesson: Search Scales with Compute

Rich Sutton’s 2019 essay, “The Bitter Lesson,” argues that general methods can outperform hand-crafted domain knowledge when given enough data and compute.
Sutton identifies learning and search as methods that scale; nearest-neighbor retrieval is one way to search for similar examples.
Search underlies systems such as Google, where finding relevant items across large collections is central.

5:40 Formalizing Exact and K-Nearest-Neighbor Queries

Given a dataset X in R^D, a query q, and a distance function, exact nearest-neighbor search returns the point x* minimizing distance(x, q).
The lecture uses Euclidean distance, while noting that related methods can support cosine or Mahalanobis distance after suitable transformations.
A K-nearest-neighbor query returns the K closest points, useful when a single match is insufficient.

11:00 Preprocessing and Practical Uses of Nearest Neighbors

A data structure S(X) lets a system spend time preprocessing the dataset instead of scanning all points for every query.
Search systems can find duplicate or near-duplicate documents, including overly similar homework submissions.
For prediction, retrieving several labeled neighbors lets a model aggregate their known outcomes rather than rely on one match.

17:30 Sorted Binary Trees Deliver Logarithmic Search in One Dimension

In R¹, sort the points and build a balanced binary tree whose nodes store split values.
A query follows the appropriate side of each split in O(log N) time, then checks adjacent sorted points to select the true nearest neighbor.
The structure uses O(N) space and takes O(N log N) time to build, dominated by sorting.

25:00 Skip Lists Use Random Promotions to Narrow Search

A skip list maintains sorted linked-list layers, promoting roughly half the points at random at each successive level.
Queries traverse the sparse upper layers to narrow their interval, then inspect a constant number of candidates at the bottom.
The randomized structure uses roughly linear space and supports logarithmic expected query time, providing an analogy for modern layered graph indexes.

29:40 Voronoi Diagrams Precompute Exact Neighbors in Two Dimensions

A Voronoi diagram partitions the plane so every location in a cell has the same nearest dataset point.
In two dimensions, the diagram can be built in O(N log N) time and stored in O(N) space; point-location structures support O(log N) queries.
For Euclidean distance, diagram edges are perpendicular bisectors and vertices are equidistant from three points.

37:00 Voronoi Complexity Exposes the Curse of Dimensionality

In dimension D, Voronoi structure can require N^ceil(D/2) space, which is quadratic already at D = 3.
The rapidly growing representation prevents extending the efficient two-dimensional exact-search approach directly to high dimensions.
Approximate nearest-neighbor search relaxes the requirement: the returned point may be up to a factor of 1 + ε farther away than the exact nearest point.

39:10 KD-Trees Prune Regions for Approximate Nearest Neighbors

A KD-tree recursively splits space with axis-aligned boundaries, typically dividing the points roughly in half at each split.
After finding a candidate near the query, the search prunes cells that cannot intersect the candidate-distance ball, adjusted for the allowed approximation factor.
Alternating-coordinate KD-trees often work in roughly 10–12 dimensions; strategic split directions can extend some implementations to around 100–200 dimensions.

48:30 High-Dimensional Balls and Boxes Explain Search Difficulty

An axis-aligned box enclosing a unit-radius Euclidean ball has volume 2^D, while the ball’s volume relative to that box shrinks sharply as D grows.
The box’s 2^D corners occupy an increasingly significant share of its volume, making box-based partitions poor approximations to spherical distance neighborhoods.
This geometric mismatch helps explain why KD-tree-style decompositions become ineffective as dimensionality rises.

57:10 Locality-Sensitive Hashing Makes High-Dimensional Search Sublinear

Locality-sensitive hashing (LSH) uses randomized hash functions designed to map nearby points together more often than distant points.
Its approximate-search costs depend strongly on ε but, apart from reading coordinates, can avoid direct dependence on dimension D.
For ε = 1, the lecture gives illustrative bounds of about N^(8/7) space and N^(1/7) query time; optimized FALCONN implementations can beat scanning on large, high-dimensional datasets.

1:03:20 HNSW Replaces Theory-First Expectations with Practical Performance

Hierarchical Navigable Small World (HNSW) graphs became highly effective in practice, despite earlier theoretical concerns about graph-search failures.
The lecture presents HNSW as a high-dimensional extension of the skip-list idea: sparse upper levels guide the search toward a dense base layer.
HNSW-style systems outperformed the theoretically motivated LSH approach in practical high-dimensional search benchmarks.

1:05:00 Build a K-Nearest-Neighbor Graph as HNSW’s Base Layer

The base structure connects each dataset point to a small number of its nearest neighbors, forming a K-nearest-neighbor graph.
A query can start at an entry point and greedily move to a neighbor closer to the query.
Greedy traversal alone can stop at a local minimum or require many hops, which motivates additional search mechanisms.

1:09:00 Beam Search Maintains Multiple Candidate Paths

Beam search keeps the top K candidates found so far instead of committing to just the single closest current node.
Retaining multiple candidates—for example, a beam width of 10—makes it less likely that the search gets trapped in a local minimum.
The candidate beam can continue exploring graph neighbors until no better reachable candidates remain.

1:12:00 Layered HNSW Graphs Power Modern Vector Databases

HNSW randomly promotes a fraction of points into sparser upper layers, where longer-range graph edges improve navigation; search descends toward the full K-nearest-neighbor graph at the bottom.
FAISS, Microsoft DiskANN, Qdrant, and Pinecone are examples of systems associated with modern vector search; implementations also use reduced precision in upper layers to save memory and computation.
Approximate nearest- and K-nearest-neighbor search is now practical for high-dimensional vectors using Euclidean or cosine distance, and related distance measures can often be transformed into compatible forms.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, UofU Data Science.