Media identification system with fingerprint database balanced according to search loads

• US 9,292,514 B2
• Filed: 04/24/2014
• Issued: 03/22/2016
• Est. Priority Date: 06/11/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Seet, Nicholas, Johnson, Rob, Smallman, Joshua, Cahan, Adam
• Primary Examiner(s): PENG, HUAWEN A
• Application Number:
  US14/260,747
• Publication Number:
  US 20140236952A1
• Time in Patent Office: 698 Days
• Field of Search: 707/671
• US Class Current: 1/1
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures

Abstract

A media identification system generates reference fingerprints for known media samples and stores the reference fingerprints in a reference database. The media identification system uses the reference fingerprints to match a fingerprint generated from an unknown media sample to identify that unknown sample. When storing new reference fingerprints in the reference database, partitions of the database are selected to balance the search loads on the database when it is used by the media identification system. For example, the selected partitions may be determined based at least in part on the access rates of the partitions by the media identification system. New reference fingerprints will tend to be placed in partitions that have relatively lower access rates that the other partitions, which will tend to balance the search loads on the partitions by the media identification system.

Claims

1. A method comprising:

identifying, by a computing device, a candidate set of reference fingerprints, the identifying of the candidate set of reference fingerprints occurs based on their occurrence in predefined buckets, each bucket referencing a group of reference fingerprints that share the same bit values at certain bit positions specified by a template associated with the each bucket;

marking, by the computing device, buckets in the predefined buckets that contain reference fingerprints whose bit values match a test fingerprint at the bit positions specified in the corresponding template, each marked bucket indicating an increased probability that the reference fingerprints referenced by that bucket are a match to the test fingerprint; and

determining, by the computing device, that the candidate set of reference fingerprints match the test fingerprint by identifying a group of reference fingerprints as the candidate set of reference fingerprints based on their recurrence in highest marked buckets.

2. The method of claim 1, wherein the reference fingerprints are referenced in a plurality of different buckets in the predefined buckets.

3. The method of claim 1, further comprising storing, by the computing device, media fingerprints in a reference database comprising a plurality of partitions, each partition storing reference fingerprints generated from known media samples, the reference fingerprints used to identify unknown digital media samples.

4. The method of claim 1, wherein the reference fingerprints in the candidate set of reference fingerprints comprises digital fingerprints for a portion of audio content.

5. The method of claim 1, wherein the reference fingerprints in the candidate set of reference fingerprints comprises digital fingerprints for a portion of video content.

6. The method of claim 3, wherein the reference database further comprises metadata associated with each reference fingerprint.

7. The method of claim 6, wherein the metadata further comprises information about digital media content attributed to the reference fingerprints.

8. The method of claim 3, wherein the reference database further comprises a number of indexes that can be used to identify the candidate set of reference fingerprints that match the test fingerprint.

9. The method of claim 1, wherein partial matches between the test fingerprint and the corresponding reference fingerprint are sufficient for identifying the test fingerprint.

10. A non-transitory computer readable storage medium for tangibly storing thereon computer instructions for execution by a processor, the computer instructions for performing the steps of:

identifying, by the processor, a candidate set of reference fingerprints, the identifying of the candidate set of reference fingerprints occurs based on their occurrence in predefined buckets, each bucket referencing a group of reference fingerprints that share the same bit values at certain bit positions specified by a template associated with the each bucket;

marking, by the processor, buckets in the predefined buckets that contain reference fingerprints whose bit values match a test fingerprint at the bit positions specified in the corresponding template, each marked bucket indicating an increased probability that the reference fingerprints referenced by that bucket are a match to the test fingerprint; and

determining, by the processor, that the candidate set of reference fingerprints match the test fingerprint by identifying a group of reference fingerprints as the candidate set of reference fingerprints based on their recurrence in highest marked buckets.

11. The medium of claim 10, wherein the reference fingerprints are referenced in a plurality of different buckets in the predefined buckets.

12. The medium of claim 10, further comprising storing, by the computing device, media fingerprints in a reference database comprising a plurality of partitions, each partition storing reference fingerprints generated from known media samples, the reference fingerprints used to identify unknown digital media samples.

13. The medium of claim 10, wherein the reference fingerprints in the candidate set of reference fingerprints comprises digital fingerprints for a portion of audio content.

14. The medium of claim 10, wherein the reference fingerprints in the candidate set of reference fingerprints comprises digital fingerprints for a portion of video content.

15. The medium of claim 12, wherein the reference database further comprises metadata associated with each reference fingerprint.

16. The medium of claim 15, wherein the metadata further comprises information about digital media content attributed to the reference fingerprints.

17. The medium of claim 12, wherein the reference database further comprises a number of indexes that can be used to identify the candidate set of reference fingerprints that match the test fingerprint.

18. The medium of claim 10, wherein partial matches between the test fingerprint and the corresponding reference fingerprint are sufficient for identifying the test fingerprint.

19. A system comprising:

a processor;

a reference database in communication with the processor, the reference database comprising a plurality of partitions, each partition storing a set of reference fingerprints generated from known media samples; and

a fingerprint matching algorithm, executed by the processor, configured to identify a candidate set of reference fingerprints, the identifying of the candidate set of reference fingerprints occurs based on their occurrence in predefined buckets, each bucket referencing a group of reference fingerprints that share the same bit values at certain bit positions specified by a template associated with the each bucket, configured to mark buckets in the predefined buckets that contain reference fingerprints whose bit values match a test fingerprint at the bit positions specified in the corresponding template, each marked bucket indicating an increased probability that the reference fingerprints referenced by that bucket are a match to the test fingerprint, and configured to determine that the candidate set of reference fingerprints match the test fingerprint by identifying a group of reference fingerprints as the candidate set of reference fingerprints based on their recurrence in highest marked buckets.

20. The system of claim 19, wherein the fingerprint matching algorithm performs partial matching between the test fingerprint and the corresponding reference fingerprint to identify the test fingerprint.