Patent Document ID: 8352494
Application ID: 12632681
Patent Status: 1

Claim One:
1. A computer-implemented method comprising: generating a tree-based representation of an image corpus on a root server, the tree-based representation including a plurality of leaf nodes, each leaf node representing one of a plurality of image clusters in the image corpus in a multi-dimensional feature space; distributing the plurality of image clusters among a plurality of leaf servers configured to communicate with the root server, such that each image cluster is assigned to a leaf server in the plurality of leaf servers; mapping the each image cluster from the multi-dimensional feature space to a hash space such that each image in the each image cluster is represented by a respective hash value in the hash space; searching the tree-based representation on the root server to identify one or more image clusters to which a received query image belongs in the multi-dimensional feature space, wherein the query image and images in the identified one or more image clusters are each represented by the respective hash value in the hash space; forwarding the received query image from the root server to one or more leaf servers that have been assigned the identified one or more image clusters; and performing a nearest-neighbor search for the query image within each of the identified one or more image clusters to identify a respective set of result images on the image cluster's assigned leaf server, wherein the nearest-neighbor search is performed according to image distance in the hash space; and wherein performing the nearest neighbor search in the hash space further comprises performing a two-stage nearest-neighbor search for the received query image within each of the identified one or more image clusters on the image cluster's assigned leaf server, and wherein said two-stage nearest-neighbor search comprises: a first stage search being performed according to distances computed using a subset of all bits of the hash values of the query image and the each image in the image cluster, and a second stage search being performed according to distances computed using all bits of the hash values of the query image and each image within a preliminary set of results produced by the first stage.