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 one or more processors may to apply a partitioning algorithm to a first subset of target feature descriptors to determine a first classifying data structure to be used when performing a visual search with respect to a query feature descriptor. The one or more processors may then apply the partitioning algorithm to a second subset of the target feature descriptors to determine a second classifying data structure to be used when performing the visual search with respect to the same query feature descriptor.