Distributed Image Search

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for distributed nearest-neighbor search for image retrieval are disclosed. An example distributed image retrieval system includes a root server and a plurality of leaf servers. The root server controls the clustering of images in the image corpus, and determines the assignment of image clusters to a collection of leaf servers. Each leaf server is independently configured to perform a two-stage nearest-neighbor search in a locality-sensitive hash space for a received query image within the leaf server's assigned images clusters. Thus, the distributed image retrieval system is modular and amendable to tuning, modifications, duplication, and replacement on a per-server basis. In addition, the design of the image retrieval system allows flexible load balancing among the leaf servers.

What is claimed is: 
     
         1 . (canceled) 
     
     
         2 . A computer-implemented method comprising:
 receiving a query image;   generating a representation of the query image;   identifying multiple image clusters that correspond to the query image;   identifying multiple image search servers that correspond to the multiple image clusters that correspond to the query image;   sending the representation of the query image to each of the multiple image search servers that correspond to the multiple image clusters that correspond to the query image;   receiving, from each of the multiple image search servers that correspond to the multiple image clusters that correspond to the query image, data representing one or more result images; and   providing a response to the query image based on at least one of the result images.   
     
     
         3 . The method of  claim 2 , wherein identifying multiple image search servers that correspond to the multiple image clusters that correspond to the query image, comprises:
 identifying, for each of the multiple image clusters that correspond to the query image, an image search server that is assigned to the image cluster.   
     
     
         4 . The method of  claim 3 , wherein identifying, for each of the multiple image clusters that correspond to the query image, an image search server that is assigned to the image cluster, comprises:
 obtaining a mapping of assignments of the multiple image clusters to the image search servers; and   identifying the image search server that is assigned to the image cluster based on the mapping.   
     
     
         5 . The method of  claim 3 , wherein identifying, for each of the multiple image clusters that correspond to the query image, an image search server that is assigned to the image cluster, comprises:
 determining that the image cluster is assigned to two or more multiple image search servers; and   selecting one of the two or more multiple image search servers as the identified image search server.   
     
     
         6 . The method of  claim 5 , wherein selecting one of the two or more multiple image search servers as the identified image search server, comprises:
 selecting one of the two or more image search servers as the identified image search server based on at least one of a current load on the one of the two or more image search servers, available resources on the one of the two or more image search servers, search speed requirements, a geographical location of the one of the two or more image search servers, or a relative likelihood the one of the two or more image search servers corresponds to images that are responsive to the query image.   
     
     
         7 . The method of  claim 2 , further comprising:
 receiving first data corresponding to images of an image corpus, the images defined in an image space, the first data representing the images transformed from the image space into a multi-dimensional feature space;   partitioning the first data to generate the multiple image clusters in the multi-dimensional feature space, each image cluster representing a respective portion of the images of the image corpus;   assigning each of the image clusters to one or more respective image search servers; and   wherein partitioning the first data is based on a tree-based representation of the image corpus, and wherein the tree-based representation comprises one of a K-d tree, a spill-tree, a metric tree, a vantage-point tree, or a hybrid tree.   
     
     
         8 . The method of  claim 7 , wherein the tree-based representation comprises a spill-tree and at least one image in the image corpus is included in more than one of the plurality of image clusters. 
     
     
         9 . The method of  claim 7 , wherein identifying multiple image clusters that correspond to the query image comprises:
 traversing the tree-based representation of the image corpus by using the transformed query image to reach one or more leaf nodes of the tree-based representation, the one or more leaf nodes representing one or more of the image clusters.   
     
     
         10 . The method of  claim 7 , wherein assigning each of the image clusters to one or more respective image search servers comprises:
 determining a respective estimated search volume for each of the image clusters; and   assigning each of the image clusters to the one or more respective image search servers according to the respective estimated search volume of the image cluster, wherein at least one image search server is assigned to more than one image cluster or at least one image cluster is duplicated on more than one image search server.   
     
     
         11 . The method of  claim 2 , further comprising:
 performing, in a hash space, a two-stage nearest-neighbor search within each of the identified image clusters to identify one or more of the result images on the image cluster's corresponding image search server.   
     
     
         12 . The method of  claim 11 , wherein performing the two-stage nearest-neighbor search within each of the identified image clusters further comprises:
 computing a hash value for the query image in the hash space;   computing a respective first distance between the query image and each image in the image cluster in the hash space, the respective first distance being based on a subset of all bits of the respective hash values for the query image and the image in the image cluster;   identifying a preliminary set of result images based on the respective first distances;   computing a respective second distance between the query image and each image in the preliminary set of result images, the respective second distance being based on all bits of the respective hash values for the query image and the image in the preliminary set of result images; and   identifying a final set of result images from the preliminary set of result images based on the respective second distances, the final set of result images being ranked according to the respective second distances.   
     
     
         13 . The method of  claim 2 , further comprising:
 applying one or more filtering criteria to the result images to remove one or more inappropriate or duplicate images from the result images.   
     
     
         14 . A system comprising:
 one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
 receiving a query image; 
 generating a representation of the query image; 
 identifying multiple image clusters that correspond to the query image; 
 identifying multiple image search servers that correspond to the multiple image clusters that correspond to the query image; 
 sending the representation of the query image to each of the multiple image search servers that correspond to the multiple image clusters that correspond to the query image; 
 receiving, from each of the multiple image search servers that correspond to the multiple image clusters that correspond to the query image, data representing one or more result images; and 
 providing a response to the query image based on at least one of the result images. 
   
     
     
         15 . The system of  claim 14 , wherein identifying multiple image search servers that correspond to the multiple image clusters that correspond to the query image, comprises:
 identifying, for each of the multiple image clusters that correspond to the query image, an image search server that is assigned to the image cluster.   
     
     
         16 . The system of  claim 15 , wherein identifying, for each of the multiple image clusters that correspond to the query image, an image search server that is assigned to the image cluster, comprises:
 obtaining a mapping of assignments of the multiple image clusters to the image search servers; and   identifying the image search server that is assigned to the image cluster based on the mapping.   
     
     
         17 . The system of  claim 15 , wherein identifying, for each of the multiple image clusters that correspond to the query image, an image search server that is assigned to the image cluster, comprises:
 determining that the image cluster is assigned to two or more multiple image search servers; and   selecting one of the two or more multiple image search servers as the identified image search server.   
     
     
         18 . The system of  claim 14 , the operations further comprising:
 receiving first data corresponding to images of an image corpus, the images defined in an image space, the first data representing the images transformed from the image space into a multi-dimensional feature space;   partitioning the first data to generate the image clusters in the multi-dimensional feature space, each image cluster representing a respective portion of the images of the image corpus;   assigning each of the image clusters to one or more respective image search servers; and   wherein partitioning the first data is based on a tree-based representation of the image corpus, and wherein the tree-based representation comprises one of a K-d tree, a spill-tree, a metric tree, a vantage-point tree, or a hybrid tree.   
     
     
         19 . The system of  claim 18 , wherein the tree-based representation comprises a spill-tree and at least one image in the image corpus is included in more than one of the plurality of image clusters. 
     
     
         20 . The system of  claim 18 , wherein identifying the one or more image clusters to which the query image most likely belongs comprises:
 traversing the tree-based representation of the image corpus by using the transformed query image to reach one or more leaf nodes of the tree-based representation, the one or more leaf nodes representing the one or more image clusters.   
     
     
         21 . A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:
 receiving a query image;   generating a representation of the query image;   identifying multiple image clusters that correspond to the query image;   identifying multiple image search servers that correspond to the multiple image clusters that correspond to the query image;   sending the representation of the query image to each of the multiple image search servers that correspond to the multiple image clusters that correspond to the query image;   receiving, from each of the multiple image search servers that correspond to the multiple image clusters that correspond to the query image, data representing one or more result images; and   providing a response to the query image based on at least one of the result images.