used to score the images (performed by `extract-feature`, `random-permute`, and `vector-quantize` functions in Table \[alg:mapping\]). In an easy search, as the query has many common words with its nearest neighbor and not with other images, after processing only some small percentage of the features the score of the true matching image becomes significantly larger than the mean of the histogram. However, when the query shares its words with many images, i.e., a difficult search, a higher percentage of the words need to cast their vote to find the true match. We stop the feature mapping once the distance between the peak of the histogram to the average of the other bins is greater than some threshold (`stop-time` function). Other stopping rules might be defined, which are described in Section \[sec:rules\].

Our method is different from the naive approach of stopping after quantizing a fixed percentage of the features. Based on our stopping criterion when the search is easy, the VQ stops sooner, otherwise it stops after processing more features. With the naive approach, a search is forced to stop even if more processing is required to find the nearest neighbor.

0 The problem that we study in this paper can 