A Reliable Order-Statistics-Based Approximate Nearest Neighbor Search Algorithm

Luisa Verdoliva, Davide Cozzolino, Giovanni Poggi

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.

Common space partitioning strategies, including Voronoi (a), k-d trees (b), and various grids (c-f).

Reliability and Efficiency

To mitigate the "boundary problem" where the true nearest neighbor might fall into an adjacent partition, ROSANNA employs two strategies:

  1. Multiple Bases: Data is projected onto multiple randomly rotated coordinate systems to create multiple hash tables.
  2. Multi-probe Search: The algorithm intelligently explores statistically likely neighboring cones.
Directional lobes illustrating the concept of conic partitioning, which is more natural for high-dimensional spherical data distributions.

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

Abstract

We propose a new algorithm for fast approximate nearest neighbor search based on the properties of ordered vectors. Data vectors are classified based on the index and sign of their largest components, thereby partitioning the space in a number of cones centered in the origin. The query is itself classified, and the search starts from the selected cone and proceeds to neighboring ones. Overall, the proposed algorithm corresponds to locality sensitive hashing in the space of directions, with hashing based on the order of components. Thanks to the statistical features emerging through ordering, it deals very well with the challenging case of unstructured data, and is a valuable building block for more complex techniques dealing with structured data. Experiments on both simulated and real-world data prove the proposed algorithm to provide a state-of-the-art performance.
BibTeX
@article{verdoliva2015reliable,
  author = {Luisa Verdoliva and Davide Cozzolino and Giovanni Poggi},
  title = {{A Reliable Order-Statistics-Based Approximate Nearest Neighbor Search Algorithm}},
  journal = {IEEE Trans. Image Process.},
  year = {2015},
  doi = {10.1109/tip.2016.2624141},
}
Figure