Yes, being able to compute quickly is especially important in reducing query latency, much more so than during indexing. What stood out for me in the paper was that out of box performance of VGG (trained on imagenet alone) was as good as fine tuned alexnet.

I am interested in assessing if there are any tricks that could be used when querying from a mobile device. In such cases feature extraction can be performed on the device itself, with only feature vectors sent over the network. In case of pinterest, another special case is that a lot queries are performed on images already present in the system. The user simply readjusts the bounding box to highlight the object of interest. In this case they can simply pre-compute 4~20 crops per image. Online feature computation is much more expensive / complicated than offline.