Introduction
Approximate Nearest Neighbor (ANN) search is a fundamental task in computer vision and image processing, essential for applications ranging from image retrieval to patch-based denoising. In high-dimensional spaces, exact search becomes computationally prohibitive due to the "curse of dimensionality." Existing methods typically optimize for either memory efficiency (e.g., Product Quantization) or search speed (e.g., k-d trees, Locality Sensitive Hashing). However, these techniques often struggle with unstructured data—data lacking clear clusters—or require expensive classification steps.
Methodology: The ROSANNA Algorithm
The Reliable Order-Statistics based Approximate NN search Algorithm (ROSANNA) introduces a novel partitioning strategy based on the properties of order statistics.
Conic Partitioning
Unlike traditional methods that use random hyperplanes or centroids, ROSANNA partitions the search space into "cones." A vector is classified based on the indices and signs of its $G$ largest components. This approach leverages the observation that the largest components of high-dimensional vectors contain the majority of the vector's energy, making them reliable signatures for hashing.
Reliability and Efficiency
To mitigate the "boundary problem" where the true nearest neighbor might fall into an adjacent partition, ROSANNA employs two strategies:
- Multiple Bases: Data is projected onto multiple randomly rotated coordinate systems to create multiple hash tables.
- Multi-probe Search: The algorithm intelligently explores statistically likely neighboring cones.
The classification process is highly efficient, requiring only partial sorting and sign checking, which is significantly faster than calculating distances to multiple centroids.
Experimental Results
ROSANNA was evaluated on synthetic (Gaussian, Uniform, Laplace) and real-world datasets (UBC SIFT, IRISA SIFT, MNIST).
- Unstructured Data: On i.i.d. Gaussian data, ROSANNA outperformed established techniques like FLANN and IVFADC, often by an order of magnitude in speed for equivalent accuracy.
- Real-World Performance: For UBC SIFT and MNIST datasets, the algorithm achieved approximately double the speed of competitors in the 0.9–0.99 precision range.
- Application Case Study: In copy-move forgery detection using PatchMatch, ROSANNA reduced CPU processing time by 60% without sacrificing detection accuracy.
Conclusion
ROSANNA demonstrates that sorting components by magnitude creates a robust structure even in seemingly random data. By partitioning space into cones rather than hypercubes, it aligns more naturally with the spherical distribution of high-dimensional data. While primarily optimized for unstructured data, extensions like ROSANNA+ incorporate k-means to handle highly clustered datasets, making it a versatile tool for modern ANN search challenges.
Summary updated