Visual geo-localization is the task of determining the location where a photo was taken, exploiting only visual information. This task plays an important role in numerous applications, such as in the categorization of images for photo collections, augmented reality, and for the localization of mobile robots, therefore it is an active area of research. The task is commonly approached as an image retrieval problem: given a query, its location is inferred by performing a similarity search, via k-nearest neighbour (kNN) over a database of geotagged images. While this solution allows to achieve remarkable results in moderately sized problems, it does not scale well to large maps.