Performing a geo-visual search is disclosed. A query feature vector associated with a query tile is obtained. A lookup is performed at least in part by using a key derived from the query feature vector. A list of candidate feature vectors is obtained based at least in part on the lookup. Based at least in part on a comparison of the query feature vector against at least some of the candidate feature vectors in the obtained list, a tile that is visually similar to the query tile is determined. The determined tile is provided as output.