Full-length video fingerprinting

1. A method for generating a full-length fingerprint of a video, the method executed by at least one computer system, the method comprising:

accessing a plurality of subfingerprints for the video, wherein each subfingerprint encodes features of a corresponding segment of the video;

generating a plurality of subhistograms, wherein each subhistogram encodes a frequency of a subfingerprint feature for a subset of the plurality of subfingerprints;

concatenating the plurality of subhistograms to generate a histogram, wherein the histogram encodes a frequency of the subfingerprint feature for the plurality of subfingerprints;

generating the full-length video fingerprint based on the histogram; and

storing the full-length video fingerprint to memory.

2. The method of claim 1 , wherein each subfingerprint comprises a vector of min-hash values.

3. The method of claim 2 , further comprising:

applying a wavelet transform to a segment of the video to create an array of wavelet coefficients; and

applying a min-hash procedure to the array of wavelet coefficients to create the subfingerprint corresponding to the segment of the video.

4. The method of claim 1 , wherein generating the plurality of subhistograms comprises:

dividing the plurality of subfingerprints into a plurality of partitions, wherein each partition comprises a subset of the plurality of subfingerprints;

determining a number of subfingerprints in each partition that includes the subfingerprint feature in a subfingerprint position.

5. The method of claim 1 , wherein each subhistogram comprises a multi-dimensional vector with dimensions comprising:

a subfingerprint position dimension;

a min-hash value dimension; and

a number of occurrences dimension.

6. The method of claim 1 , wherein generating the histogram further comprises:

generating a plurality of bins, each bin specifying a subhistogram feature;

associating each generated bin with a count; and

populating the histogram, wherein the histogram comprises identifiers of the generated bins in association with the corresponding counts.

7. The method of claim 1 , wherein generating the full-length video fingerprint based on the histogram comprises:

applying a hashing procedure to the histogram to generate the full-length video fingerprint.

8. The method of claim 7 , wherein applying a hashing procedure to the histogram to generate the full-length video fingerprint comprises:

assigning a weight to each of a plurality of histogram features; and

applying a first hash function to a number of altered versions of each histogram feature to generate a plurality of outputs for the first hash function.

9. The method of claim 8 , wherein the number of altered versions of a histogram feature is based on the weight assigned to the histogram feature.

10. The method of claim 8 , wherein applying a hashing procedure to the histogram to generate the full-length video fingerprint further comprises:

determining a smallest output for the first hash function; and

populating a first entry of the full-length video fingerprint with a first hash input, wherein the first hash input corresponds to the determined smallest output for the first hash function.

11. The method of claim 10 , wherein applying a hashing procedure to the histogram to generate the full-length video fingerprint further comprises:

applying a second hash function to the number of altered versions of each histogram feature to generate a plurality of outputs for the second hash function;

determining a smallest output for the second hash function; and

populating a second entry of the full-length video fingerprint with a second hash input, wherein the second hash input corresponds to the determined smallest output for the second hash function.

12. The method of claim 11 , wherein the first hash function and the second hash function are part of a family of hash functions, the first hash function having a first seed value and the second hash function having a second seed value.

13. The method of claim 1 , further comprising:

assigning the video to a cluster of videos based on the generated full-length video fingerprint.

14. The method of claim 13 , wherein assigning the video to a cluster of videos based on the generated full-length fingerprint comprises:

calculating a number of matching entries for the full-length video fingerprint for the video and a second full-length video fingerprint for a second video.

15. A non-transitory computer-readable storage medium storing computer-executable code, the computer-executable code when executed by a processor causing the processor to perform a process for generating a full-length fingerprint of a video, the process comprising:

accessing a plurality of subfingerprints for the video, wherein each subfingerprint encodes features of a corresponding segment of the video;

generating a plurality of subhistograms, wherein each subhistogram encodes a frequency of a subfingerprint feature for a subset of the plurality of subfingerprints;

concatenating the plurality of subhistograms to generate a histogram, wherein the histogram encodes a frequency of the subfingerprint feature for the plurality of subfingerprints;

generating the full-length video fingerprint based on the histogram; and

storing the full-length video fingerprint to memory.

16. The non-transitory computer-readable storage medium of claim 15 , wherein each subfingerprint comprises a vector of min-hash values.

17. The non-transitory computer-readable storage medium of claim 16 , the process further comprising:

applying a wavelet transform to a segment of the video to create an array of wavelet coefficients; and

applying a min-hash procedure to the array of wavelet coefficients to create the subfingerprint corresponding to the segment of the video.

18. The non-transitory computer-readable storage medium of claim 15 , wherein generating the plurality of subhistograms comprises:

dividing the plurality of subfingerprints into a plurality of partitions, wherein each partition comprises a subset of the plurality of subfingerprints;

determining a number of subfingerprints in each partition that includes the subfingerprint feature in a subfingerprint position.

19. The non-transitory computer-readable storage medium of claim 15 , wherein each subhistogram comprises a multi-dimensional vector with dimensions comprising:

a subfingerprint position dimension;

a min-hash value dimension; and

a number of occurrences dimension.

20. The non-transitory computer-readable storage medium of claim 15 , wherein generating the histogram further comprises:

generating a plurality of bins, each bin specifying a subhistogram feature;

associating each generated bin with a count; and

populating the histogram, wherein the histogram comprises identifiers of the generated bins in association with the corresponding counts.

21. The non-transitory computer-readable storage medium of claim 15 , wherein generating the full-length video fingerprint based on the histogram comprises:

applying a hashing procedure to the histogram to generate the full-length video fingerprint.

22. The non-transitory computer-readable storage medium of claim 21 , wherein applying a hashing procedure to the histogram to generate the full-length video fingerprint comprises:

assigning a weight to each of a plurality of histogram features; and

applying a first hash function to a number of altered versions of each subhistogram feature to generate a plurality of outputs for the first hash function.

23. The non-transitory computer-readable storage medium of claim 22 , wherein the number of altered versions of a subhistogram feature is based on the weight assigned to the subhistogram feature.

24. The non-transitory computer-readable storage medium of claim 22 , wherein applying a hashing procedure to the master histogram to generate the full-length video fingerprint further comprises:

determining a smallest output for the first hash function; and

populating a first entry of the full-length video fingerprint with a first hash input, wherein the first hash input corresponds to the determined smallest output for the first hash function.

25. The non-transitory computer-readable storage medium of claim 24 , wherein applying a hashing procedure to the master histogram to generate the full-length video fingerprint further comprises:

applying a second hash function to the number of altered versions of each subhistogram feature to generate a plurality of outputs for the second hash function;

determining a smallest output for the second hash function; and

populating a second entry of the full-length video fingerprint with a second hash input, wherein the second hash input corresponds to the determined smallest output for the second hash function.

26. The non-transitory computer-readable storage medium of claim 25 , wherein the first hash function and the second hash function are part of a family of hash functions, the first hash function having a first seed value and the second hash function having a second seed value.

27. The non-transitory computer-readable storage medium of claim 15 , the process further comprising:

assigning the video to a cluster of videos based on the generated full-length video fingerprint.

28. The non-transitory computer-readable storage medium of claim 27 , wherein assigning the video to a cluster of videos based on the generated full-length fingerprint comprises:

calculating a number of matching entries for the full-length video fingerprint for the video and a second full-length video fingerprint for a second video.