Media identification system with fingerprint database balanced according to search loads
First Claim
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.
8 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20)
-
Specification