Choosing neighbors (Algorithms 3 & 4)·6 min
Why closest-M isn't enough
0 / 1
Closest-M has a fatal flaw on clustered data — and real vector data is always clustered. Imagine the new point sits between two dense clusters. The M closest candidates are all in the near cluster. Now your point has no edge to the far cluster, and neither do its neighbors. The graph develops disconnected pockets, and a greedy walk arriving from the wrong side can never reach the far cluster. Recall craters.
SIMPLE picks all-near (bad) vs HEURISTIC keeps a far edge (good)
cluster A cluster B
(. . . .) q (. . . .)
new
SIMPLE (M=4): q -> all 4 nearest, all in A [no bridge to B]
HEURISTIC(M=4): q -> 3 in A + 1 in B [B stays reachable]