---
abstract: 'We propose a technique to improve the search efficiency of the bag-of-words method for image retrieval. We introduce a notion of difficulty for the image matching problems and propose methods that reduce the amount of computations required for the feature vector-quantization task in BoW by exploiting the fact that easier queries need less computational resources. Measuring the difficulty of a query and stopping the search accordingly is formulated as a stopping problem. We introduce stopping rules that terminate the image search depending on the difficulty of each query, thereby significantly reducing the computational cost. Our experimental results show the effectiveness of our approach when it is applied to appearance-based localization problem.'
author:
- 'Kiana Hajebi and Hong Zhang[^1]'
title: '**Stopping Rules for Bag-of-Words Image Search and Its Application in Appearance-Based Localization** '
---

INTRODUCTION
============

Bag-of-Words (BoW) was originally proposed for document retrieval. In recent years, the method has been successfully applied to image retrieval tasks in computer vision community [@sivic; @nister]. The method is attractive because of its efficient image representation and retrieval. BoW represents an image as a sparse vector of visual words, and thus images can be searched efficiently using an inverted index file system. 