In Tineye's data set, wouldn't rotational issues tend to be edge cases since the vast majority of images on the web are already properly oriented? And given that most of the edge cases are likely to involve 90, 180 or 270 degrees of rotation, the additional computational requirements to cover those would appear to be significantly less than required for true non-translational calculation - i.e. wouldn't rotating the low frequency image 90 degrees and generating a second hash + creating reverse order hashes of the original and second hash work?
It seems to me that for applications such as cryptography where the costs of false positives are high, a SIFT algorithm makes sense. But for a free consumer oriented search tool, might it be considered overkill?
Link to SIFT: http://en.wikipedia.org/wiki/Scale-invariant_feature_transfo...
I guess my take on TinEye is that cases "when you need it" may be cases outside their target current market segment. Getting people to use their service is probably more important than using a sophisticated algorithm.