In general, techniques are described for performing a vocabulary-based visual search using multi-resolution feature descriptors. A device may comprise one or more processors configured to perform the techniques. The processors may generate a hierarchically arranged data structure to be used when classifying objects included within a query image based on multi-resolution query feature descriptor extracted from the query image at a first scale space resolution and a second scale space resolution. The hierarchically arranged data structure may represent a first query feature descriptor of the multi-resolution feature descriptor extracted at the first scale space resolution and a second corresponding query feature descriptor of the multi-resolution feature descriptor extracted at the second scale space resolution hierarchically arranged according to the first scale space resolution and the second scale space resolution. The processors may then perform a visual search based on the generated data structure.