Media identification system with fingerprint database balanced according to search loads

• US 8,713,068 B2
• Filed: 06/11/2009
• Issued: 04/29/2014
• Est. Priority Date: 06/11/2009
• Status: Expired due to Fees

• 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:
  US12/483,222
• Publication Number:
  US 20100318587A1
• Time in Patent Office: 1,783 Days
• Field of Search: 707/705, 707/968, 707/802
• US Class Current: 707/802
• 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:

storing media fingerprints in a reference database comprising a plurality of partitions, each partition storing a set of reference fingerprints generated from known media samples, the reference fingerprints used to identify unknown digital media samples;

monitoring access rates of the partitions of the reference database by a media identification system, wherein an access rate of a partition is determined as the average number of reference fingerprints on that partition that are included in a candidate set of fingerprints, wherein the candidate set of fingerprints comprises a subset of reference fingerprints in the partition that match a test fingerprint associated with an unknown digital media sample;

receiving a request to store one or more new reference fingerprints in the reference database;

selecting a partition of the reference database based at least in part on the access rates of the partitions; and

storing the new reference fingerprints in the selected partition of the reference database,

wherein the storing media fingerprints in a reference database further comprises indexing the reference fingerprints in the database by a characteristic of the reference fingerprints, and

grouping reference fingerprints having the same indexed characteristic in the same partition of the reference database.

2. The method of claim 1, wherein each partition is a logically defined data repository of the reference database.

3. The method of claim 1, wherein the reference database further comprises metadata about the known media samples corresponding to the reference fingerprints in the reference database.

4. The method of claim 1, wherein the access rate for a particular partition of the reference database comprises a number of requests to read reference fingerprints from the partition over a designated time period.

5. The method of claim 1, wherein one or more of the reference fingerprints are generated from known audio samples.

6. The method of claim 1, wherein one or more of the reference fingerprints are generated from known video samples.

7. 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:

storing media fingerprints in a reference database comprising a plurality of partitions, each partition storing a set of reference fingerprints generated from known media samples, the reference fingerprints used to identify unknown digital media samples;

monitoring access rates of the partitions of the reference database by a media identification system, wherein an access rate of a partition is determined as the average number of reference fingerprints on that partition that are included in a candidate set of fingerprints, wherein the candidate set of fingerprints comprises a subset of reference fingerprints in the partition that match a test fingerprint associated with an unknown digital media sample;

receiving a request to store one or more new reference fingerprints in the reference database;

selecting a partition of the reference database based at least in part on the access rates of the partitions; and

storing the new reference fingerprints in the selected partition of the reference database,

wherein the storing media fingerprints in a reference database further comprises indexing the reference fingerprints in the database by a characteristic of the reference fingerprints, and

grouping reference fingerprints having the same indexed characteristic in the same partition of the reference database.

8. The non-transitory computer readable storage medium of claim 7, wherein each partition is a logically defined data repository of the reference database.

9. The non-transitory computer readable storage medium of claim 7, wherein the reference database further comprises metadata about the known media samples corresponding to the reference fingerprints in the reference database.

10. The non-transitory computer readable storage medium of claim 7, wherein the access rate for a particular partition of the reference database comprises a number of requests to read reference fingerprints from the partition over a designated time period.

11. The non-transitory computer readable storage medium of claim 7, wherein one or more of the reference fingerprints are generated from known audio samples.

12. The non-transitory computer readable storage medium of claim 7, wherein one or more of the reference fingerprints are generated from known video samples.

13. A media identification 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;

a fingerprint matching algorithm, executed by the processor, configured to match an unknown media sample by comparing a test fingerprint generated from the unknown media sample with one or more reference fingerprints in the reference database;

a fingerprint generation algorithm, executed by the processor, configured to generate new reference fingerprints from known media samples, and further configured to store new reference fingerprints in partitions of the reference database selected at least in part on the access rates of the partitions by the fingerprint matching algorithm, wherein an access rate of a partition is determined as the average number of reference fingerprints on that partition that are included in a candidate set of fingerprints, wherein the candidate set of fingerprints comprises a subset of reference fingerprints in the partition that match the test fingerprint,

wherein the reference database further comprises an index that indexes the reference fingerprints by a characteristic of the reference fingerprints, and

wherein the reference fingerprints having the same indexed characteristic are grouped in the same partition of the reference database.

14. The system of claim 13, wherein each partition is a logically defined data repository of the reference database.

15. The system of claim 13, wherein the reference database further comprises metadata about the known media samples corresponding to the reference fingerprints in the reference database.

16. The system of claim 13, wherein the access rate for a particular partition of the reference database comprises a number of requests to read reference fingerprints from the partition over a designated time period.

17. The system of claim 13, wherein one or more of the reference fingerprints are generated from known audio samples.

18. The system of claim 13, wherein one or more of the reference fingerprints are generated from known video samples.