A pruning criterion decides whether a branch can be skipped during approximate nearest-neighbor search. It compares the branch’s closest possible distance with the current nearest-neighbor distance, trading some accuracy for fewer visited branches and dataset points. section 10.4.3
Apply the criterion as follows:
- Maintain the current nearest neighbor and its distance from the query point. section 10.4.3
- Compute the smallest possible distance from the query point to the branch’s bounding envelope. section 10.4.3
- With approximation error ε, where 0.0 ≤ ε ≤ 0.5, prune unless that possible distance is smaller than the current distance divided by 1+ε. section 10.4.3
For ordinary nearest-neighbor search, ε=0 gives the exact-style comparison. Increasing ε makes pruning more aggressive while guaranteeing that the returned neighbor is no farther than a factor of 1+ε from the true nearest neighbor. section 10.4.3
A missed true neighbor
With ε≈0.25, traversal can prune the branch containing the true neighbor when that neighbor lies outside the approximated query region, while returning a closer-visited candidate.
