1. A computer-readable storage medium, excluding signals per se, comprising instructions stored thereon that, responsive to execution by a computing device, direct the computing device to perform operations comprising: transforming components of a image descriptor into transformed components in a transform domain; quantizing the transformed components; generating a compact representation of the image descriptor based, at least in part, on the quantized components; and responsive to the generating, constructing, at query time, a one-dimensional look-up table that stores a partial distance between two or more of the quantized components.