Approximation error controls the accuracy–search-cost trade-off in approximate nearest-neighbor search. A parameter ϵ, where 0.0 ≤ ϵ ≤ 0.5, permits early termination while bounding the returned distance. section 10.4.3
For a query point P:
- If the true nearest neighbor N is at distance d, the returned point Q is guaranteed to be no farther than (1+ϵ)d. section 10.4.3
- Prune a branch only when its closest possible point is farther than the current nearest-neighbor distance divided by 1+ϵ. section 10.4.3
- Apply the same guarantee to n-nearest-neighbor search by measuring the distance of the n-th neighbor. section 10.4.3
Missing the true neighbor
With ϵ approximately 0.25, a traversal can prune the branch containing the true nearest neighbor J when J lies outside the permitted approximate query region, returning a closer-traversed alternative instead.
