Ranking over hashes

• US 9,110,923 B2
• Filed: 03/03/2011
• Issued: 08/18/2015
• Est. Priority Date: 03/03/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yee, Yangli Hector, Ioffe, Sergey, Bengio, Samy
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US13/040,168
• Publication Number:
  US 20150169633A1
• Time in Patent Office: 1,629 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for training an image ranking model to rank images based on hashes of their contents using a lookup table. An image training set is received. An image ranking model is trained with the training set by generating an image hash for each image of the ordered pair of images based on one or more features extracted from the image, computing a first score for a first image hash of a first image of the pair and a second score for a second image hash of a second image of the pair using the image ranking model, determining whether to update the image ranking model based on the first score and the second score, and updating the image ranking model using an update value based on the first score and the second score.

Claims

1. A computer-implemented method comprising:

receiving a search query;

identifying a lookup table corresponding to the search query;

for each image in a collection of images;

generating an image hash for the image based on one or more features extracted from the image, wherein the image hash comprises a plurality of hash characters, and

computing a score for the image hash using the lookup table, wherein computing the score for each image hash comprises summing lookup table weights for each hash character of the plurality of hash characters, and wherein the lookup table includes a first index that corresponds to the lookup table value of each hash character, and a second index that corresponds to a position of each hash character in the image hash;

ordering the images by the score of each image hash; and

providing a group of the ordered images as search results responsive to the search query.

2. The method of claim 1, wherein summing a lookup table weights for each of a plurality of hash characters of the image hash comprises identifying the lookup table weight for each hash character by using the first index and second index.

3. The method of claim 1, wherein each hash character corresponds to a bit string.

4. The method of claim 1, wherein the search query is a text query and the ordered images represent a relevance of each image to the text query.

5. The method of claim 1, wherein the search query is an image query and the ordered images represent a similarity of each image to the image query.

6. The method of claim 1, further comprising:

receiving a second search query, the second search query being different from the search query;

identifying a second lookup table corresponding to the second search query, wherein the second lookup table is different from the lookup table; and

providing a group of ordered images as search results responsive to the second query based on scores computed for each image using the second lookup table.

7. A system comprising:

one or more computers; and

a computer-readable storage device having stored thereon instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving a search query;

identifying a lookup table corresponding to the search query;

for each image in a collection of images;

generating an image hash for the image based on one or more features extracted from the image, wherein the image hash comprises a plurality of hash characters, and

computing a score for the image hash using the lookup table, wherein computing the score for each image hash comprises summing lookup table weights for each hash character of the plurality of hash characters, and wherein the lookup table includes a first index that corresponds to the lookup table value of each hash character, and a second index that corresponds to a position of each hash character in the image hash;

ordering the images by the score of each image hash; and

providing a group of the ordered images as search results responsive to the search query.

8. The system of claim 7, wherein summing a lookup table weight for each of a plurality of hash characters of the image hash comprises identifying the lookup table weight for each hash character by using the first index and second index.

9. The system of claim 7, wherein each hash character corresponds to a bit string.

10. The system of claim 7, wherein the search query is a text query and the ordered images represent a relevance of each image to the text query.

11. The system of claim 7, wherein the search query is an image query and the ordered images represent a similarity of each image to the image query.

12. The system of claim 7, wherein the instructions when executed by the one or more computers further cause the one or more computers to perform operations comprising:

receiving a second search query, the second search query being different from the search query;

identifying a second lookup table corresponding to the second search query, wherein the second lookup table is different from the lookup table; and

providing a group of ordered images as search results responsive to the second query based on scores computed for each image using the second lookup table.

13. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a search query;

identifying a lookup table corresponding to the search query;

for each image in a collection of images;

generating an image hash for the image based on one or more features extracted from the image, wherein the image hash comprises a plurality of hash characters, and

computing a score for the image hash using the lookup table, wherein computing the score for each image hash comprises summing lookup table weights for each hash character of the plurality of hash characters, and wherein the lookup table includes a first index that corresponds to the lookup table value of each hash character, and a second index that corresponds to a position of each hash character in the image hash;

ordering the images by the score of each image hash; and

providing a group of the ordered images as search results responsive to the search query.

14. The computer storage medium of claim 13, wherein summing a lookup table weight for each of a plurality of hash characters of the image hash comprises identifying the lookup table weight for each hash character by using the first index and second index.

15. The computer storage medium of claim 13, wherein each hash character corresponds to a bit string.

16. The computer storage medium of claim 13, wherein the search query is a text query and the ordered images represent a relevance of each image to the text query.

17. The computer storage medium of claim 13, wherein the search query is an image query and the ordered images represent a similarity of each image to the image query.

18. The computer storage medium of claim 13, further comprising instructions to perform operations comprising:

receiving a second search query, the second search query being different from the search query;

identifying a second lookup table corresponding to the second search query, wherein the second lookup table is different from the lookup table; and

providing a group of ordered images as search results responsive to the second query based on scores computed for each image using the second lookup table.