Sub-query evaluation for image search

• US 9,152,652 B2
• Filed: 03/14/2013
• Issued: 10/06/2015
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rosenberg, Charles J., Gao, Mingchen, Duerig, Thomas J., Gu, Kunlong
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US13/828,254
• Publication Number:
  US 20150169631A1
• Time in Patent Office: 936 Days
• Field of Search: 1/1, 707/999.005, 707/999.107, 707/723, 715/811
• US Class Current: 1/1
• CPC Class Codes: G06F 16/50 of still image data

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for identifying images responsive to a search phrase are disclosed. In one aspect, a method includes identifying a set of responsive images for a search phrase that includes two or more terms. Interaction rankings are determined for images in the set of responsive images. Two or more sub-queries are created based on the search phrase. Sub-query model rankings are determined for images in the set of responsive images. A search phrase score is determined for the image relevance model. Based on the search phrase scores for the sub-queries, one of the sub-query models is selected as a model for the search phrase.

Claims

1. A method performed by data processing apparatus, the method comprising:

identifying responsive images for a search phrase that includes two or more terms;

determining, by one or more processors, interaction rankings for each of the responsive images based on a number of user interactions with the responsive image;

creating, by one or more processors, two or more sub-queries based on the search phrase, the sub-queries each being a proper subset of the two or more terms;

for each sub-query from the two or more sub-queries;

determining, by one or more processors, sub-query model rankings for the responsive images based on a sub-query model for the sub-query and visual features of the responsive images, the sub-query model being an image relevance model for the sub-query; and

determining, by one or more processors, a search phrase score for the sub-query model, the search phrase score being based on a measure of similarity between positions of the responsive images in each of the interaction rankings and the sub-query model rankings; and

selecting, based on the search phrase scores for the sub-queries, one of the sub-query models as a model for the search phrase, the selected sub-query model having a search phrase score that meets a threshold search phrase score.

2. The method of claim 1, wherein determining interaction rankings for images in the responsive images comprises:

ranking a first image from the responsive images as a highest ranked image, the first image having a highest number of user interactions among the responsive images;

ranking a second image from the responsive images as a second highest ranked image, the second image having a second highest number of user interactions among the responsive images; and

ranking each unranked image in the responsive images in descending order according to the number of user interactions with the unranked image.

3. The method of claim 1, further comprising creating an interaction histogram based on the interaction rankings and the numbers of user interactions with the responsive images.

4. The method of claim 3, further comprising creating a sub-query histogram based on the sub-query model rankings and the number of user interactions with the responsive images.

5. The method of claim 4, wherein determining a search phrase score comprises:

determining a level of match between the interaction histogram and the sub-query histogram; and

determining the search phrase score based on the level of match between the interaction histogram and the sub-query histogram.

6. The method of claim 1, further comprising:

obtaining, for the selected sub-query model, an additional search phrase score specifying a measure of similarity between interaction rankings of other images responsive to another search phrase and sub-query model rankings of the other images based on the selected sub-query model; and

determining a global search phrase score for the selected sub-query model, the global search phrase score being determined based on an aggregate measure of the search phrase score and the additional search phrase score.

7. The method of claim 6, further comprising:

determining that the global search phrase score for the selected sub-query model meets a global search phrase score threshold;

identifying the sub-query corresponding to the selected sub-query model as a global sub-query based on the determination that the global search phrase score meets the global search phrase threshold; and

ranking images for at least one additional search phrase that includes the sub-query and at least one other term based on the selected sub-query model.

8. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

identifying responsive images for a search phrase that includes two or more terms;

determining interaction rankings for each of the responsive images based on a number of user interactions with the responsive image;

creating two or more sub-queries based on the search phrase, the sub-queries each being a proper subset of the two or more terms;

for each sub-query from the two or more sub-queries;

determining sub-query model rankings for the responsive images based on a sub-query model for the sub-query and visual features of the responsive images, the sub-query model being an image relevance model for the sub-query; and

determining a search phrase score for the sub-query model, the search phrase score being based on a measure of similarity between positions of the responsive images in each of the interaction rankings and the sub-query model rankings; and

selecting, based on the search phrase scores for the sub-queries, one of the sub-query models as a model for the search phrase, the selected sub-query model having a search phrase score that meets a threshold search phrase score.

9. The computer storage medium of claim 8, wherein determining interaction rankings for each of the responsive images comprises:

ranking a first image from the responsive images as a highest ranked image, the first image having a highest number of user interactions among the responsive images;

ranking a second image from the responsive images as a second highest ranked image, the second image having a second highest number of user interactions among the responsive images; and

ranking each unranked image in the responsive images in descending order according to the number of user interactions with the unranked image.

10. The computer storage medium of claim 8, wherein the instructions cause the data processing apparatus to perform operations comprising creating an interaction histogram based on the interaction rankings and the numbers of user interactions with the responsive images.

11. The computer storage medium of claim 10, wherein the instructions cause the data processing apparatus to perform operations comprising creating a sub-query histogram based on the sub-query model rankings and the number of user interactions with the responsive images.

12. The computer storage medium of claim 11, wherein determining a search phrase score comprises:

determining a level of match between the interaction histogram and the sub-query histogram; and

determining the search phrase score based on the level of match between the interaction histogram and the sub-query histogram.

13. The computer storage medium of claim 8, wherein the instructions cause the data processing apparatus to perform operations comprising:

obtaining, for the selected sub-query model, an additional search phrase score specifying a measure of similarity between interaction rankings of other images responsive to another search phrase and sub-query model rankings of the other images based on the selected sub-query model; and

determining a global search phrase score for the selected sub-query model, the global search phrase score being determined based on an aggregate measure of the search phrase score and the additional search phrase score.

14. A system comprising:

a data store; and

one or more data processing apparatus that interact with the data store and execute instructions that cause the one or more computers to perform operations comprising;

identifying responsive images for a search phrase that includes two or more terms;

determining interaction rankings for each of the responsive images based on a number of user interactions with the responsive image;

creating two or more sub-queries based on the search phrase, the sub-queries each being a proper subset of the two or more terms;

for each sub-query from the two or more sub-queries;

determining sub-query model rankings for the responsive images based on a sub-query model for the sub-query and visual features of the responsive images, the sub-query model being an image relevance model for the sub-query; and

determining a search phrase score for the sub-query model, the search phrase score being based on a measure of similarity between positions of the responsive images in each of the interaction rankings and the sub-query model rankings; and

selecting, based on the search phrase scores for the sub-queries, one of the sub-query models as a model for the search phrase, the selected sub-query model having a search phrase score that meets a threshold search phrase score.

15. The system of claim 14, wherein determining interaction rankings for each of the responsive images comprises:

ranking a first image from the responsive images as a highest ranked image, the first image having a highest number of user interactions among the responsive images;

ranking a second image from the responsive images as a second highest ranked image, the second image having a second highest number of user interactions among the responsive images; and

ranking each unranked image in the responsive images in descending order according to the number of user interactions with the unranked image.

16. The system of claim 14, wherein the instructions cause the one or more data processing apparatus to perform operations comprising creating an interaction histogram based on the interaction rankings and the numbers of user interactions with the responsive images.

17. The system of claim 16, wherein the instructions cause the one or more data processing apparatus to perform operations comprising creating a sub-query histogram based on the sub-query model rankings and the number of user interactions with the responsive images.

18. The system of claim 17, wherein determining a search phrase score comprises:

determining a level of match between the interaction histogram and the sub-query histogram; and

determining the search phrase score based on the level of match between the interaction histogram and the sub-query histogram.

19. The system of claim 14, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

obtaining, for the selected sub-query model, an additional search phrase score specifying a measure of similarity between interaction rankings of other images responsive to another search phrase and sub-query model rankings of the other images based on the selected sub-query model; and

determining a global search phrase score for the selected sub-query model, the global search phrase score being determined based on an aggregate measure of the search phrase score and the additional search phrase score.

20. The system of claim 19, wherein the instructions cause the one or more data processing apparatus to perform operations comprising:

determining that the global search phrase score for the selected sub-query model meets a global search phrase score threshold;

identifying the sub-query corresponding to the selected sub-query model as a global sub-query based on the determination that the global search phrase score meets the global search phrase threshold; and

ranking images for at least one additional search phrase that includes the sub-query and at least one other term based on the selected sub-query model.