words are identified in the query image, they are used as indices into the image database, to directly retrieve the images that share the same words.

When the vocabulary is large, the vector-quantization process can be a computationally expensive task in real-time localization. Considerable research has been done to speed up the search; some papers [@fabmap] do approximate nearest-neighbor search using structures like vocabulary trees [@nister]; some methods reduce the number of local image features by selecting only a fraction of features that are highly discriminative [@Achar; @BoRF]; another group makes use of more compact feature descriptors like [@bi-BoW; @fabmap]. In this paper, we first show that some image retrieval tasks are [*easier*]{} for BoW method. The hardness criteria, defined later, concerns how distinctive the image query is among all images in the dataset. Given this criteria, we show that the BoW search can be terminated earlier for easier queries. This means, in such queries, mapping only a portion of features can be sufficient to yield a relatively good result. The stopping rule saves considerable amount of computational resources.

The intuition behind this is that when there are many similar images to the query image, in terms of the number 