10-605 · Randomized algorithms 2 · k-NN search

Approximate k-NN with a hierarchical J-means tree

Cluster the N points into J clusters, then run J-means again inside each cluster, down to depth d. To search for a query qx, find the centroid closest to qx among its J siblings at each level (O(dJ) distance computations), then scan only the points in that leaf (O(N/J^d)). Click or drag anywhere on the plot to move qx.

points N

clusters per node J

depth d

neighbors k

data

randomness

point x query qx centroid (bigger = higher level) cells qx descends into tree k-NN exact k-NN

Search for qx

This query

Vector quantization

The path through the tree is a compact code for qx: its leaf centroid is an approximate encoding of qx, like an LSH signature.

Average over random queries

N	J	d	k	avg leaf size	distance comps	vs. N	recall@k

Each run draws 300 queries from the same distribution as the data and adds one row, so you can compare settings. "distance comps" is dJ + |leaf| per query, averaged.

Algorithm

Build(points, depth):
  if depth = 0: return a leaf holding points
  run J-means on points → centroids c₁,…,c_J, clusters C₁,…,C_J
  child_i = Build(C_i, depth − 1)   for i = 1,…,J
Search(qx, k):
  node = root
  while node is not a leaf:                     O(J) per level, d levels
    i = argmin_i dist(qx, c_i) over node's children
    node = child_i
  return the k points x in node closest to qx   O(N/J^d)