Approximate similarity search retrieves sufficiently similar objects without insisting on the exact nearest result. It targets large, high-dimensional datasets—such as image collections—where exact tree searches become impractical because of the curse of dimensionality. section 10.0 section 10.4.3
Approximation exchanges some result accuracy for faster search through several complementary strategies:
- Reduce dimensionality by projecting objects into a lower-dimensional space with PCA or the Discrete Fourier Transform. section 10.4.3
- Traverse fewer branches by applying more aggressive pruning, accepting that the true nearest neighbor may be missed. section 10.4.3
- Terminate early when a result passes a distance threshold or when further traversal is unlikely to improve it. section 10.4.3
Approximate image retrieval
Given an image query and an SS-tree, aggressive pruning can skip a branch containing the true nearest image when its region appears too distant. The search returns a faster, possibly nonoptimal neighbor instead. section 10.4.3
