of common words they share, the search becomes more difficult as more processing is required to find the closest match candidate. Whereas when the query image has only a few match candidates, i.e., it shares its visual words with only a few images, the search becomes easy as vector-quantizing only a small number of features is sufficient to find the closest match to the query. By exploiting this fact, we can stop the vector-quantization when the search is easy and the nearest neighbor to the query is easy to find. Our method acts as an approximate image search algorithm. Our experimental results show that the accuracy decreases only slightly while the computational cost decreases dramatically.

Our approach can be best compared with the approach of Cummins and Newman [@accel_fabmap] who use concentration inequalities (Bennett’s inequality in their case) for early bail-out in multi-hypothesis testing that excludes unlikely location hypotheses from further evaluation. However, we use a different bail-out strategy for the process of vector-quantization. In the next section, we briefly review the image representation and the inverted-index search algorithm used in BoW framework. This is followed by a review of the localization algorithms that employ BoW for the image search. 