Selection of hash lookup keys for efficient retrieval

• US 8,184,953 B1
• Filed: 02/23/2009
• Issued: 05/22/2012
• Est. Priority Date: 02/22/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Covell, Michele, Ioffe, Sergey, Baluja, Shumeet, Marwood, David
• Primary Examiner(s): Tran, Thai
• Assistant Examiner(s): Gracia, Gary
• Application Number:
  US12/391,153
• Time in Patent Office: 1,184 Days
• Field of Search: 380/201, 386/248, 707/2, 707/3, 707/104, 707/100, 707/101, 382/209
• US Class Current: 386/248
• CPC Class Codes: G06F 16/71 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G11B 27/28 by using information signals recorded by the same method as the main recording G11B27/22 takes precedence

Abstract

Videos are received and indexed based on fingerprints generated for the videos, using lookup keys which correspond to sub portions of the reference fingerprints. Specifically, a set of lookup keys is selected such that the number of reference fingerprints such that the clumping associated with the associated each of the lookup keys is minimized. Clumping occurs when a number of reference identifiers associated with a lookup key exceeds a maximum value.

Claims

1. A computer-implemented method for indexing a set of reference videos, the method executed by one or more computer systems and comprising:

receiving a set of training reference fingerprints based on a set of training reference videos,

each training reference fingerprint comprising a sequence of fingerprint values representing a time localized portion of a training reference video from the set of training reference videos;

identifying a set of keys contained in the set of training reference fingerprints, each key

comprising a subset of the fingerprint values;

selecting a subset of the set of keys based, in part, on a selection algorithm, wherein the selection algorithm evaluates a plurality of subsets of the set of keys based on a reward function, wherein the reward function quantifies, in part, an amount of clumping associated with each subset of the set of keys;

generating a reference index for indexing a set of reference videos based on the subset of keys;

and storing the reference index.

2. The method of claim 1, wherein selecting the subset of keys comprises:

selecting a key of the set of keys;

generating a set of reward values associated with the plurality of subsets of the set of keys based on the reward function, wherein each reward value represents an expected benefit associated with adding the selected key to a subset of keys;

and adding the selected key to a subset of keys of the plurality of subsets of keys based on the set of reward values, wherein the selected key is added to the subset of keys associated with a reward value that indicates a maximum benefit associated with adding the selected key to the subset of keys.

3. The method of claim 2, wherein selecting a subset of keys further comprises;

generating a plurality of reward values associated with the plurality of subsets of keys based, in part, on the reward function, wherein each of the plurality of reward values indicate, in part, an amount of clumping associated with a subset of keys;

and selecting the subset of keys of the plurality of subsets of keys associated with a reward value which indicates a minimum amount of clumping associated with the subset of keys.

4. The method of claim 1, wherein selecting the subset of keys comprises:

iteratively generating the plurality of subsets of keys according to a permutation function;

generating a plurality of selection values associated with the plurality of subsets of keys based, in part, on the reward function, wherein each of the plurality of values indicates, in part, a degree of clumping associated with a subset of keys;

and selecting the subset of keys of the plurality of subsets of keys associated with selection value which indicates a minimum amount of clumping associated with the subset of key.

5. The method of claim 1, further comprising:

generating a plurality of values associated with the subset of keys, wherein each value

indicates an amount of clumping associated with a key;

identifying a key of the subset of key associated with a value of the plurality of values, the value indicating a large amount of clumping;

generating one or more split keys associated with the key, wherein the one or more split keys comprise the key and at least one additional fingerprint value;

and storing data indicating the one or more split keys.

6. The method of claim 5, wherein generating a reference index for indexing a set of reference videos based on the subset of keys comprises allocating memory associated with each key of the subset of keys and further comprising:

allocating memory associated with the one or more split keys.

7. The method of claim 5, further comprising:

receiving a set of reference fingerprints based on a reference video, each reference fingerprint comprising a sequence of fingerprint values representing a time localized portion of the reference video;

identifying a set of keys contained in the set of training reference fingerprints, each key comprising a subset of the fingerprint values;

identifying a set of bins associated with the set of keys based on the reference index, wherein each bin specifies a number of reference videos the key is associated with;

and modifying the reference index to include the one or more split keys associated with the lookup key responsive to determining that the number of reference videos the key is associated with exceeds a threshold value.

8. A non-transitory computer-readable storage medium encoded with executable computer program code for indexing a set of reference videos, the program code comprising program code for:

receiving a set of training reference fingerprints based on a set of training reference videos,

each training reference fingerprint comprising a sequence of fingerprint values representing a time localized portion of a training reference video from the set of training reference videos;

identifying a set of keys contained in the set of training reference fingerprints, each key comprising a subset of the fingerprint values;

selecting a subset of the set of keys based, in part, on a selection algorithm, wherein the selection algorithm evaluates a plurality of subsets of the set of keys based on a reward function, wherein the reward function quantifies, in part, an amount of clumping associated with each subset of the set of keys;

generating a reference index for indexing a set of reference videos based on the subset of keys;

and storing the reference index.

9. The medium of claim 8, wherein program code for selecting the subset of keys comprises program code for:

selecting a key of the set of keys;

generating a set of reward values associated with the plurality of subsets of the set of keys based on the reward function, wherein each reward value represents an expected benefit associated with adding the selected key to a subset of keys;

and adding the selected key to a subset of keys of the plurality of subsets of keys based on the set of reward values, wherein the selected key is added to the subset of keys associated with a reward value that indicates a maximum benefit associated with adding the selected key to the subset of keys.

10. The medium of claim 9, wherein program code for selecting a subset of keys further comprises program code for:

generating a plurality of reward values associated with the plurality of subsets of keys based, in part, on the reward function, wherein each of the plurality of reward values indicate, in part, an amount of clumping associated with a subset of keys;

And selecting the subset of keys of the plurality of subsets of keys associated with a reward value which indicates a minimum amount of clumping associated with the subset of keys.

11. The medium of claim 9, wherein selecting the subset of keys comprises:

iteratively generating the plurality of subsets of keys according to a permutation function;

generating a plurality of selection values associated with the plurality of subsets of keys based, in part, on the reward function, wherein each of the plurality of values indicates, in part, a degree of clumping associated with a subset of keys;

and selecting the subset of keys of the plurality of subsets of keys associated with selection value which indicates a minimum amount of clumping associated with the subset of key.

12. The medium of claim 9, further comprising:

generating a plurality of values associated with the subset of keys, wherein each value indicates an amount of clumping associated with a key;

identifying a key of the subset of key associated with a value of the plurality of values, the value indicating a large amount of clumping;

generating one or more split keys associated with the key, wherein the one or more split keys comprise the key and at least one additional fingerprint value; and

storing data indicating the one or more split keys.

13. The medium of claim 12, wherein generating a reference index for indexing a set of reference videos based on the subset of keys comprises allocating memory associated with each key of the subset of keys and further comprising:

allocating memory associated with the one or more split keys.

14. The medium of claim 13, further comprising:

receiving a set of reference fingerprints based on a reference video, each reference fingerprint comprising a sequence of fingerprint values representing a time localized portion of the reference video;

identifying a set of keys contained in the set of training reference fingerprints, each key comprising a subset of the fingerprint values;

identifying a set of bins associated with the set of keys based on the reference index, wherein each bin specifies a number of reference videos the key is associated with;

and modifying the reference index to include the one or more split keys associated with the lookup key responsive to determining that the number of reference videos the key is associated with exceeds a threshold value.

15. A computer system for indexing a set of reference videos, the computer system comprising:

a memory;

a processor;

and a training module stored in the memory and executable by the processor to;

receive a set of training reference fingerprints based on a set of training reference videos,

each training reference fingerprint comprising a sequence of fingerprint values representing a time localized portion of a training reference video from the set of training reference videos;

identify a set of keys contained in the set of training reference fingerprints, each key comprising a subset of the fingerprint values;

select a subset of the set of keys based, in part, on a selection algorithm, wherein the selection algorithm evaluates a plurality of subsets of the set of keys based on a reward function, wherein the reward function quantifies, in part, an amount of clumping associated with each subset of the set of keys;

generate a reference index for indexing a set of reference videos based on the subset of keys;

and store the reference index.

16. The computer system of claim 15, wherein the training module is further executable to:

select a key of the set of keys;

generate a set of reward values associated with the plurality of subsets of the set of keys based on the reward function, wherein each reward value represents an expected benefit associated with adding the selected key to a subset of keys;

and add the selected key to a subset of keys of the plurality of subsets of keys based on the set of reward values, wherein the selected key is added to the subset of keys associated with a reward value that indicates a maximum benefit associated with adding the selected key to the subset of keys.

17. The computer system of claim 16, wherein the training module is further executable to:

generate a plurality of reward values associated with the plurality of subsets of keys based, in part, on the reward function, wherein each of the plurality of reward values indicate, in part, an amount of clumping associated with a subset of keys;

and select the subset of keys of the plurality of subsets of keys associated with a reward value which indicates a minimum amount of clumping associated with the subset of keys.

18. The computer system of claim 15, wherein the training module is further executable to:

iteratively generate the plurality of subsets of keys according to a permutation function;

generate a plurality of selection values associated with the plurality of subsets of keys based, in part, on the reward function, wherein each of the plurality of values indicates, in part, a degree of clumping associated with a subset of keys;

and select the subset of keys of the plurality of subsets of keys associated with selection value which indicates a minimum amount of clumping associated with the subset of key.

19. The computer system of claim 15, wherein the training module is further executable to:

generate a plurality of values associated with the subset of keys, wherein each value indicates an amount of clumping associated with a key;

identify a key of the subset of key associated with a value of the plurality of values, the value indicating a large amount of clumping;

generate one or more split keys associated with the key, wherein the one or more split keys comprise the key and at least one additional fingerprint value; and

store data indicating the one or more split keys.

20. The computer system of claim 19, wherein generating a reference index for indexing a set of reference videos based on the subset of keys comprises allocating memory associated with each key of the subset of keys and training module is further executable to:

allocate memory associated with the one or more split keys.

21. The computer system of claim 20, further comprising an indexing module stored in the memory and executable by the processor to:

receive a set of reference fingerprints based on a reference video, each reference fingerprint comprising a sequence of fingerprint values representing a time localized portion of the reference video;

identifying a set of keys contained in the set of training reference fingerprints, each key comprising a subset of the fingerprint values;

identifying a set of bins associated with the set of keys based on the reference index, wherein each bin specifies a number of reference videos the key is associated with;

and modifying the reference index to include the one or more split keys associated with the lookup key responsive to determining that the number of reference videos the key is associated with exceeds a threshold value.