Abstract

The overreaching goals in large-scale image retrieval are big- ger, better and cheaper. For systems based on local features we show how to get both efficient geometric verification of every match and un- precedented speed for the low sparsity situation. Large-scale systems based on quantized local features usually process the index one term at a time, forcing two separate scoring steps: First, a scoring step to find candidates with enough matches, and then a geo- metric verification step where a subset of the candidates are checked. Our method searches through the index a document at a time, veri- fying the geometry of every candidate in a single pass. We study the be- havior of several algorithms with respect to index density—a key element for large-scale databases. In order to further improve the efficiency we also introduce a new new data structure, called the counting min-tree, which outperforms other approaches when working with low database density, a necessary condition for very large-scale systems. We demonstrate the effectiveness of our approach with a proof of concept system that can match an image against a database of more than 90 billion images in just a few seconds.