Scoring hash functions

• US 9,122,705 B1
• Filed: 03/15/2012
• Issued: 09/01/2015
• Est. Priority Date: 03/15/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ioffe, Sergey
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Rayyan, Susan F
• Application Number:
  US13/421,750
• Time in Patent Office: 1,265 Days
• Field of Search: None
• US Class Current: 1/1
• 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 scoring hash functions. In one aspect, a method includes computing one or more first performance indicators for an objective function computed on each of one or more sets of input data elements using a set of hash functions. A first overall performance indicator is computed using each of the computed performance indicators. The candidate hash function is added to the set of hash functions to generate a second set of hash functions. Second performance indicators are computed for the objective function computed on each of the sets of input data elements using the second set of hash functions. A second overall performance indicator is computed using each of the computed second performance indicators, and a score is computed for the candidate hash function using the first overall performance indicator and the second overall performance indicator.

Claims

1. A method comprising:

computing one or more first performance indicators that indicate a likelihood or a probability of an objective function correctly performing a task, wherein the one or more first performance indicators are computed on each of one or more sets of input data elements using a set of hash functions;

computing a first overall performance indicator using each of the computed first performance indicators;

adding a candidate hash function to the set of hash functions to generate a second set of hash functions;

computing one or more second performance indicators that indicate a likelihood or a probability of the objective function correctly performing the task, wherein the one or more second performance indicators are computed on each of the one or more sets of input data elements using the second set of hash functions;

computing a second overall performance indicator using each of the computed second performance indicators; and

computing, using the first overall performance indicator and the second overall performance indicator, a score that indicates a degree to which the candidate hash function improves a performance of the objective function.

2. The method of claim 1, wherein the objective function classifies the sets of input data elements using the set of hash functions and the first or second performance indicator is a likelihood of a correct classification.

3. The method of claim 2, wherein the first or second overall performance indicator is a product of the first performance indicator and the second performance indicator or a sum of a logarithm of the first performance indicator and the second performance indicator.

4. The method of claim 3, wherein the score is based on a difference in log likelihood between the second overall performance indicator and the first overall performance indicator.

5. The method of claim 1, wherein the objective function ranks the sets of input data elements using the set of hash functions and the first or second performance indicator is a likelihood of a correct ranking.

6. The method of claim 5, wherein the sets of input data elements are image training triplets, wherein each image training triplet includes a query image Q, a first image A, and a second image B, wherein the first or second performance indicator is a measure of the likelihood that a distance function using the set of hash functions will correctly rank the query image Q of each image training triplet as more similar to the first image A of each image training triplet than to the second image B of each image training triplet.

7. The method of claim 6, wherein the likelihood of a correct triplet ranking is computed based at least in part on a distance between each Q and each A and a distance between each Q and each B.

8. The method of claim 1, wherein the score is based on a difference between the first overall performance indicator and the second overall performance indicator.

9. The method of claim 1, wherein the first or second overall performance indicator is a product of the first performance indicator and the second performance indicator or a sum of a logarithm of the first performance indicator and the second performance indicator.

10. 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;

computing one or more first performance indicators that indicate a likelihood or a probability of an objective function correctly performing a task, wherein the one or more first performance indicators are computed on each of one or more sets of input data elements using a set of hash functions;

computing a first overall performance indicator using each of the computed first performance indicators;

adding a candidate hash function to the set of hash functions to generate a second set of hash functions;

computing one or more second performance indicators that indicate a likelihood or a probability of the objective function correctly performing the task, wherein the one or more second performance indicators are computed on each of the one or more sets of input data elements using the second set of hash functions;

computing a second overall performance indicator using each of the computed second performance indicators; and

computing, using the first overall performance indicator and the second overall performance indicator, a score that indicates a degree to which the candidate hash function improves a performance of the objective function.

11. The system of claim 10, wherein the objective function classifies the sets of input data elements using the set of hash functions and the first or second performance indicator is a likelihood of a correct classification.

12. The system of claim 11, wherein the first or second overall performance indicator is a product of the first performance indicator and the second performance indicator or a sum of a logarithm of the first performance indicator and the second performance indicator.

13. The system of claim 12, wherein the score is based on a difference in log likelihood between the second overall performance indicator and the first overall performance indicator.

14. The system of claim 10, wherein the objective function ranks the sets of input data elements using the set of hash functions and the first or second performance indicator is a likelihood of a correct ranking.

15. The system of claim 14, wherein the sets of input data elements are image training triplets, wherein each image training triplet includes a query image Q, a first image A, and a second image B, wherein the first or second performance indicator is a measure of the likelihood that a distance function using the set of hash functions will correctly rank the query image Q of each image training triplet as more similar to the first image A of each image training triplet than to the second image B of each image training triplet.

16. The system of claim 15, wherein the likelihood of a correct triplet ranking is computed based at least in part on a distance between each Q and each A and a distance between each Q and each B.

17. The system of claim 10, wherein the score is based on a difference between the first overall performance indicator and the second overall performance indicator.

18. The system of claim 10, wherein the first or second overall performance indicator is a product of the first performance indicator and the second performance indicator or a sum of a logarithm of the first performance indicator and the second performance indicator.

19. A tangible, non-transitory computer-readable medium encoded with instructions for causing one or more processors to perform operations comprising:

computing one or more first performance indicators that indicate a likelihood or a probability of an objective function correctly performing a task, wherein the one or more first performance indicators are computed on each of one or more sets of input data elements using a set of hash functions;

computing a first overall performance indicator using each of the computed first performance indicators;

adding a candidate hash function to the set of hash functions to generate a second set of hash functions;

computing one or more second performance indicators that indicate a likelihood or a probability of the objective function correctly performing the task, wherein the one or more second performance indicators are computed on each of the one or more sets of input data elements using the second set of hash functions;

computing a second overall performance indicator using each of the computed second performance indicators; and

computing, using the first overall performance indicator and the second overall performance indicator, a score that indicates a degree to which the candidate hash function improves a performance of the objective function.