Suppose a spatial search must return the m points closest to a target. Keeping only one best point is no longer enough: the search needs the m shortest distances found so far. A bounded priority queue holds at most m candidate pairs, each containing a distance and its point. Its most useful value during the search is the distance to the furthest retained candidate. section 9.3.5 section 10.4.1
Use the queue as the search proceeds:
- Start with an infinite pruning distance. Until m candidates have been found, a branch cannot be rejected merely because it might contain another qualifying point. section 10.4.1
- Measure each visited point’s distance to the target and insert the distance–point pair. Retain at most the m closest candidates. section 9.3.5 section 10.4.1
- Once the queue has m candidates, use the furthest retained distance as the pruning radius. A branch whose region cannot contain a closer point need not be searched. section 9.3.5 section 10.4.1
From one neighbor to m neighbors
A k-d-tree search for one nearest neighbor tracks a single best distance while visiting a nearby branch and backtracking when another branch could contain a closer point. For m neighbors, replace that single result with the bounded queue. The search still backtracks, but compares branches against the distance of the m-th closest candidate rather than the closest candidate. section 9.3.5
Listing 9.10 The nNearestNeighbor method
function nNearestNeighbor(node, target, n) #1
pq ← new BoundedPriorityQueue(n) #2
pq.insert((inf, null)) #3
pq ← nNearestNeighbor(node, target, pq) #4
(nnnDist, _) ← pq.peek() #5
if nnnDist == inf then #6
pq.top()
return pq #7
function nNearestNeighbor(node, target, pq) #8
if node == null then #9
return pq
else
dist ← distance(node.point, target) #10
pq.insert((dist, node.point)) #11
if compare(target, node) < 0 then #12
closeBranch ← node.left
farBranch ← node.right
else #12
closeBranch ← node.right
farBranch ← node.left
pq ← nNearestNeighbor(closeBranch, target, pq) #13
(nnnDist, _) ← pq.peek() #14
if splitDistance(target, node) < nnnDist then #15
pq ← nNearestNeighbor(farBranch, target, pq) #16
return pq #17
The nNearestNeighbor pseudocode shows a queue sized to the requested result count, insertion of distance–point pairs, and an infinity sentinel for the initial search. section 9.3.5
The same queue-and-radius change extends SS-tree nearest-neighbor search; that implementation is left as an exercise. The queue itself stores at most m candidates, but bounding its size does not guarantee a short tree traversal: nearest-neighbor search can still visit the whole k-d tree in the worst case. section 10.4.1 section 9.3.5
