Link-based ranking of objects that do not include explicitly defined links

• US 9,977,816 B1
• Filed: 12/10/2015
• Issued: 05/22/2018
• Est. Priority Date: 04/09/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Jing, Yushi, Rowley, Henry Allan, Baluja, Shumeet
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US14/964,697
• Time in Patent Office: 894 Days
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/538 Presentation of query results
• CPC Class Codes: G06F 16/55 Clustering; Classification
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

A system determines ranking scores for objects based on “virtual” links defined for the objects. A link-based ranking score may then be calculated for the objects based on the virtual links. In one implementation, the virtual links are determined based on a metric of content-based similarity between the objects.

Claims

1. A computer-implemented method comprising:

receiving, by one or more server computers, a selection of a plurality of image feature types;

for each received image feature type, obtaining, by the one or more server computers, a set of one or more comparison functions;

receiving, by the one or more server computers, a search query from a user device;

obtaining, by the one or more server computers, a set of images that includes two or more images that are responsive to the search query from the user device;

generating, by the one or more server computers, a ranking score for the set of images, wherein generating the ranking score includes;

for each pair of images in the set of images, applying, by the one or more server computers, each of the comparison functions to one or more objects of interest identified in each image in the pair of images to generate a respective similarity score for the pair of images;

generating, by the one or more server computers, transitional probabilities for each image in the set of images based on the respective similarity scores generated for each pair of images, wherein each transitional probability is indicative of the likelihood that a user that has accessed a first image in the set of images will access a second image in the set of images;

generating, by the one or more server computers, a ranking score for each image in the set of images based on the transitional probabilities that were generated for the image;

selecting, by the one or more server computers, one or more images based on the generated ranking score;

providing, by the one or more server computers, the one or more images that were selected based on the generated ranking score for display in the user interface of the user device.

2. The method of claim 1, the method further comprising:

identifying, by the one or more server computers, a subset of one or more comparison functions from the set of one or more comparison functions based on the received feature types; and

for each pair of images in the set of images, applying, by the one or more server computers, only the subset of one or more comparison functions to one or more objects of interest identified in each image in the pair of images to generate a respective similarity score for each pair of images.

3. The method of claim 1, wherein applying, by the one or more server computers, each of the comparison functions to the pair of images to generate a respective similarity score for each pair of images includes:

identifying, by the one or more server computers, a first feature associated with a first image;

using, by the one or more server computers, one or more of the comparison functions to evaluate the first feature against a corresponding feature of each respective image in the set of images to generate a similarity score for each pair of images, wherein each similarity score is a measure of the extent that the first feature appears in a second image of each respective image pair;

generating, by the one or more server computers, a cumulative similarity score by summing the similarity score for each pair of images; and

associating, by the one or more server computers, the cumulative similarity score with the first image.

4. The method of claim 1, the method further comprising:

for each feature associated with a first image;

using, by the one or more server computers, one or more of the comparison functions to evaluate the feature of the first image against a corresponding feature of each respective image in the set of images to generate a similarity score corresponding to each feature pair, wherein each similarity score is a measure of the extent that the feature of the first image corresponds to another feature in a second image of each respective image pair; and

determining, by the one or more server computers, whether each similarity score

exceeds a predetermined similarity score threshold;

generating, by the one or more server computers, a cumulative similarity score by summing each of the similarity scores that exceed the predetermined similarity score threshold; and

associating, by the one or more server computers, the cumulative similarity score with the first image.

5. The method of claim 1, the method further comprising:

adjusting, by the one or more server computers, the transitional probability associated with a first image of a pair of images based on a query independent quality of the first image.

6. The method of claim 1, the method further comprising:

adjusting, by the one or more server computers, the transitional probability associated with a first image of a pair of images based on a determination that a first URL of a webpage that includes the first image is related to a second URL of a webpage that includes the second image.

7. The method of claim 1, wherein the one or more objects of interest are identified based on a variation in color between two or more portions of an image in the pair of images.

8. A system comprising:

one or more processors and one or more computer storage media storing instructions that are operable, when executed by the one or more processors, to cause the one or more processors to perform operations comprising;

receiving, by one or more server computers, a selection of a plurality of image feature types;

for each received image feature type, obtaining, by the one or more server computers, a set of one or more comparison functions;

receiving, by the one or more server computers, a search query from a user device;

obtaining, by the one or more server computers, a set of images that includes two or more images that are responsive to the search query from the user device;

generating, by the one or more server computers, a ranking score for the set of images, wherein generating the ranking score includes;

for each pair of images in the set of images, applying, by the one or more server computers, each of the comparison functions to the pair of images to one or more objects of interest identified in each image in the pair of images to generate a respective similarity score for the pair of images;

generating, by the one or more server computers, transitional probabilities for each image in the set of images based on the respective similarity scores generated for each pair of images, wherein each transitional probability is indicative of the likelihood that a user that has accessed a first image in the set of images will access a second image in the set of images;

generating, by the one or more server computers, a ranking score for each image in the set of images based on the transitional probabilities that were generated for the image;

selecting, by the one or more server computers, one or more images based on the generated ranking score;

providing, by the one or more server computers, the one or more images that were selected based on the generated ranking score for display in the user interface of the user device.

9. The system of claim 8, the operations further comprising:

identifying, by the one or more server computers, a subset of one or more comparison functions from the set of one or more comparison functions based on the received feature types; and

for each pair of images in the set of images, applying, by the one or more server computers, only the subset of one or more comparison functions to one or more objects of interest identified in each image in the pair of images to generate a respective similarity score for each pair of images.

10. The system of claim 8, wherein applying, by the one or more server computers, each of the comparison functions to the pair of images to generate a respective similarity score for each pair of images includes:

identifying, by the one or more server computers, first feature associated with a first image;

using, by the one or more server computers, one or more of the comparison functions to evaluate the first feature against a corresponding feature of each respective image in the set of images to generate a similarity score for each pair of images, wherein each similarity score is a measure of the extent that the first feature appears in a second image of each respective image pair;

generating, by the one or more server computers a cumulative similarity score by summing the similarity score for each pair of images; and

associating, by the one or more server computers, the cumulative similarity score with the first image.

11. The system of claim 8, the operations further comprising:

for each feature associated with a first image;

using, by the one or more server computers, one or more of the comparison functions to evaluate the feature of the first image against a corresponding feature of each respective image in the set of images to generate a similarity score corresponding to each feature pair, wherein each similarity score is a measure of the extent that the feature of the first image corresponds to another feature in a second image of each respective image pair; and

determining, by the one or more server computers, whether each similarity score exceeds a predetermined similarity score threshold;

generating, by the one or more server computers, a cumulative similarity score by summing each of the similarity scores that exceed the predetermined similarity score threshold; and

associating, by the one or more server computers, the cumulative similarity score with the first image.

12. The system of claim 8, the operations further comprising:

adjusting, by the one or more server computers, the transitional probability associated with a first image of a pair of images based on a query independent quality of the first image.

13. The system of claim 8, the operations further comprising:

adjusting, by the one or more server computers, the transitional probability associated with a first image of a pair of images based on a determination that a first URL of a webpage that includes the first image is related to a second URL of a webpage that includes the second image.

14. The system of claim 8, wherein the one or more objects of interest are identified based on a variation in color between two or more portions of an image in the pair of images.

15. A non-transitory computer-readable medium having stored thereon instructions, which, when executed by one or more computers, cause the one or more computers to perform operations of:

receiving, by one or more server computers, a selection of a plurality of image feature types;

for each received image feature type, obtaining, by the one or more server computers, a set of one or more comparison functions;

receiving, by the one or more server computers, a search query from a user device;

obtaining, by the one or more server computers, a set of images that includes two or more images that are responsive to the search query from the user device;

generating, by the one or more server computers, a ranking score for the set of images, wherein generating the ranking score includes;

for each pair of images in the set of images, applying, by the one or more server computers, each of the comparison functions to the pair of images to one or more objects of interest identified in each image in the pair of images to generate a respective similarity score for the pair of images;

generating, by the one or more server computers, transitional probabilities for each image in the set of images based on the respective similarity scores generated for each pair of images, wherein each transitional probability is indicative of the likelihood that a user that has accessed a first image in the set of images will access a second image in the set of images;

generating, by the one or more server computers, a ranking score for each image in the set of images based on the transitional probabilities that were generated for the image;

selecting, by the one or more server computers, one or more images based on the generated ranking score;

providing, by the one or more server computers, the one or more images that were selected based on the generated ranking score for display in the user interface of the user device.

16. The computer-readable medium of claim 15, the operations further comprising:

identifying, by the one or more server computers, a subset of one or more comparison functions from the set of one or more comparison functions based on the received feature types; and

for each pair of images in the set of images, applying, by the one or more server computers, only the subset of one or more comparison functions to one or more objects of interest identified in each image in the pair of images to generate a respective similarity score for each pair of images.

17. The computer-readable medium of claim 15, the operations further comprising:

for each feature associated with a first image;

using, by the one or more server computers, one or more of the comparison functions to evaluate the feature of the first image against a corresponding feature of each respective image in the set of images to generate a similarity score corresponding to each feature pair, wherein each similarity score is a measure of the extent that the feature of the first image corresponds to another feature in a second image of each respective image pair; and

determining, by the one or more server computers, whether each similarity score exceeds a predetermined similarity score threshold;

generating, by the one or more server computers, a cumulative similarity score by summing each of the similarity scores that exceed the predetermined similarity score threshold; and

associating, by the one or more server computers, the cumulative similarity score with the first image.

18. The computer readable medium of claim 15, the operations further comprising:

adjusting by the one or more server computers, the transitional probability associated with a first image of a pair of images based on a query independent quality of the first image.

19. The computer readable medium of claim 15, the operations further comprising:

adjusting, by the one or more server computers, the transitional probability associated with a first image of a pair of images based on a determination that a first URL of a webpage that includes the first image is related to a second URL of a webpage that includes the second image.

20. The computer-readable medium of claim 15, wherein the one or more objects of interest are identified based on a variation in color between two or more portions of an image in the pair of images.