What algorithm does Google use for its "Search By Image" site?
I don't know which algorithm Google uses. But, since you wanted a best guess, let me give some ideas on how a similar system could be constructed.

The whole field dealing with search-image-base-by-image is called Content Based Image Retrieval (CBIR). The idea is to, somehow, construct an image representation (not necessarily understandable by humans) that contains the information about image content.

Two basic approaches exist:


retrieval using low-level (local) features: color, texture, shape at specific parts of images (an image is a collection of descriptors of local features)
semantic approaches where an image is, in some way, represented as a collection of objects and their relations




Low-level local approach is very well researched. The best current approach extracts local features (there's a choice of feature extraction algorithm involved here) and uses their local descriptors (again, choice of descriptors) to compare the images.

In newer works, the local descriptors are clustered first and then clusters are treated as visual words -- the technique is then very similar to Google document search, but using visual words instead of letter-words.

You can think of visual words as equivalents to word roots in language: for example, the words: work, working, worked all belong to the same word root.

One of the drawbacks of these kinds of methods is that they usually under-perform on low-texture images.

I've already given and seen a lot of answers detailing these approaches, so I'll just provide links to those answers:


CBIR: 1, 2
feature extraction/description: 1, 2, 3, 4




Semantic approaches are typically based on hierarchical representations of the whole image. These approaches have not yet been perfected, especially for the general image types. There is some success in applying these kind of techniques to specific image domains.

As I am currently in the middle of research of these approaches, I can not make any conclusions. Now, that said, I explained a general idea behind these techniques in this answer.

Once again, shortly: the general idea is to represent an image with a tree-shaped structure, where leaves contain the image details and objects can be found in the nodes closer to the root of such trees. Then, somehow, you compare the sub-trees to identify the objects contained in different images.

Here are some references for different tree representations. I did not read all of them, and some of them use this kind of representations for segmentation instead of CBIR, but still, here they are:


binary partition trees and mention of min/max trees: P. Salembier, M.H.F Wilkinson: Connected Operators
binary partition trees: V. Vilaplana, F. Marques, P. Selembier: Binary Partition Trees for Object Detection
tree of shapes (component tree): P. Monasse, F. Guichard: Fast Computation of Contrast-Invariant Image Representation, C. Ballester, V. Castellis, P. Monasse: The Tree of Shapes of an Image
monotonic trees: Y. Song, A. Zhang: Analyzing scenery images by monotonic tree
edit: further digging shows that tree of shapes and monotonic tree are equivalent, except processing the image in 4-/8- (tree of shapes) or 6-connectivity (monotonic)
extrema-watershed tree: A. Vichik, R. Keshet, D. Malah: Self-dual morphology on tree semilattices and applications
constrained connectivity, alpha-trees, ultrametric waterseads: P. Soille, L. Najman: On morphological hierarchical representations for image processing and spatial data clustering