1. A computer-implemented method, the method comprising: receiving a query image; generating a feature representation of the query image; traversing a spill tree with the feature representation of the query image, wherein the spill tree comprises non-leaf nodes that each have a pair of decisional feature representations, and wherein traversing the spill tree comprises traversing the spill tree to two or more leaf nodes based on computed distances between the feature representation of the query image and decisional feature representations of one or more traversed non-leaf nodes of the spill tree; for each branch of the spill tree traversed with the feature representation of the query image, calculating accumulated spill based on, for each traversed non-leaf node of the branch, a distance from the feature representation of the query image and each decisional feature representation of the traversed non-leaf node; identifying two or more visual keys for the query image, each identified visual key corresponding to one of the two or more leaf nodes traversed to by the feature representation of the query image; ranking the two or more visual keys of the query image based on, for each visual key, the accumulated spill for the branch of the spill tree that includes the leaf node to which the visual key corresponds; identifying one or more subsets of images in a collection of images, each subset associated with a respective visual key that matches one of the highest-ranked visual keys for the query image; and generating a set of image search results for the query image corresponding to images in the identified one or more subsets of images.