An image matching system is described for finding reference images that match a query image. The image matching system performs this operation in expeditious fashion by restricting the matching to a bounding region; the bounding region, in turn, may be associated with a location at which the query image may have been captured. In addition, the image matching system provides various mechanisms that expedite adding new reference images to an image index, to thereby provide a re-enforced learning mechanism of the image matching system.