Indexing fingerprints
Example methods and systems for indexing fingerprints are described. Fingerprints may be made up of sub-fingerprints, each of which corresponds to a frame of the media, which is a smaller unit of time than the fingerprint. In some example embodiments, multiple passes are performed. For example, a first pass may be performed that compares the sub-fingerprints of the query fingerprint with every thirty-second sub-fingerprint of the reference material to identify likely matches. In this example, a second pass is performed that compares the sub-fingerprints of the query fingerprint with every fourth sub-fingerprint of the likely matches to provide a greater degree of confidence. A third pass may be performed that uses every sub-fingerprint of the most likely matches, to help distinguish between similar references or to identify with greater precision the timing of the match. Each of these passes is amenable to parallelization.
1. A system comprising:
one or more processors;
a database storing reference fingerprints; and
memory including instructions that, when executed, cause the one or more processors to at least:
obtain a query fingerprint including a plurality of sub-fingerprints;
divide the reference fingerprints into segments, each segment includes a plurality of reference sub-fingerprints;
cause a plurality of threads to determine first bit error rates by performing, in parallel, one or more operations including determining one of the first bit error rates by comparing a portion of the plurality of sub-fingerprints of the query fingerprint with a portion of the plurality of reference sub-fingerprints of a segment;
identify a first predetermined number of lowest bit error rates based on the first bit error rates, each of the first predetermined number of lowest bit error rates corresponding to one of the reference fingerprints;
in response to identifying the first predetermined number of lowest bit error rates based on the first bit error rates, for each of the first predetermined number of lowest bit error rates, determine a second bit error rate by evaluating the query fingerprint against the corresponding one of the reference fingerprints; and
provide a predetermined number of response candidates based on the second bit error rate determined for each of the first predetermined number of lowest bit error rates.
2. The system of claim 1 , wherein one or more graphics processing units (GPUs) perform the one or more operations.
3. The system of claim 1 , wherein the one or more processors are one or more central processing units (CPUs).
4. The system of claim 1 , wherein the instructions, when executed, cause the one or more processors to:
divide each of the segments into a plurality of portions, where each portion includes a plurality of the reference sub-fingerprints; and
determine the first bit error rate for each of the plurality of portions.
5. The system of claim 1 , wherein the instructions, when executed, cause the one or more processors to determine the first bit error rates by:
sub-sampling the reference fingerprints by a factor of four to determine a subset of the reference sub-fingerprints; and
comparing every fourth sub-fingerprint of the query fingerprint with sequential ones of the subset of the reference sub-fingerprints.
6. The system of claim 1 , wherein the instructions, when executed, cause the one or more processors to determine the second bit error rate for each of the first predetermined number of lowest bit error rates by:
sub-sampling the reference fingerprints by a factor of thirty-two to determine a subset of the reference sub-fingerprints; and
comparing every thirty-second sub-fingerprint of the query fingerprint with sequential ones of the subset of the reference sub-fingerprints.
7. The system of claim 1 , wherein the instructions, when executed, cause the one or more processors to cause each thread of the plurality of threads to store the first predetermined number of lowest bit error rates.
8. The system of claim 1 , wherein the instructions, when executed, cause the one or more processors to cause a first thread of the plurality of threads and a second thread of the plurality of threads to use inter-thread communications to share at least one of the sub-fingerprints of the query fingerprint.
9. The system of claim 1 , wherein the instructions, when executed, cause the one or more processors to:
sub-sample the reference fingerprints by a first factor to determine a first set of the reference sub-fingerprints;
sub-sample the query fingerprint by the first factor to determine a second set of the sub-fingerprints of the query fingerprint;
determine the first predetermined number of lowest bit error rates based on a comparison of the first set and the second set to determine a third set of the reference fingerprints, the third set corresponding to one or more of the reference fingerprints associated with the first predetermined number of lowest bit error rates;
sub-sample one or more of the third set by a second factor to determine a fourth set of the reference sub-fingerprints, the second factor greater than the first factor;
sub-sample the query fingerprint by the second factor to determine a fifth set of the sub-fingerprints of the query fingerprint; and
determine the predetermined number of response candidates based on the comparison of the fourth set and the fifth set.
10. The system of claim 4 , wherein the instructions, when executed, cause the one or more processors to:
assign each of the segments to a different server on a network; and
cause the different servers to determine the first bit error rate for the segments.
11. A method comprising:
obtaining, by one or more processors, a query fingerprint including a plurality of sub-fingerprints;
dividing a set of reference fingerprints into segments, each segment includes a plurality of reference sub-fingerprints;
causing a plurality of threads to determine first bit error rates by performing, in parallel, one or more operations including determining one of the first bit error rates by comparing a portion of the plurality of sub-fingerprints of the query fingerprint with a portion of the plurality of reference sub-fingerprints of a segment;
identifying a first predetermined number of lowest bit error rates based on the first bit error rates, each of the first predetermined number of lowest bit error rates corresponding to one of the set of reference fingerprints;
in response to identifying the first predetermined number of lowest bit error rates based on the first bit error rates, for each of the first predetermined number of lowest bit error rates, determining a second bit error rate by evaluating the query fingerprint against the corresponding one of the set of reference fingerprints; and
providing a predetermined number of response candidates based on the second bit error rate determined for each of the first predetermined number of lowest bit error rates.
12. The method of claim 11 , wherein a plurality of graphics processing units (GPUs) perform the one or more operations.
13. The method of claim 11 , wherein the one or more processors are one or more central processing units (CPUs).
14. The method of claim 11 , further including:
dividing each of the segments into a plurality of portions that each include a plurality of the reference sub-fingerprints; and
determining the first bit error rate for each of the plurality of portions.
15. The method of claim 11 , wherein determining the first bit error rates includes:
sub-sampling the reference fingerprints by a factor of four to determine a subset of the reference sub-fingerprints; and
comparing every fourth sub-fingerprint of the query fingerprint with sequential ones of the subset of the reference sub-fingerprints.
16. The method of claim 11 , wherein determining the second bit error rate determined for each of the first predetermined number of lowest bit error rates includes:
sub-sampling the reference fingerprints by a factor of thirty-two to determine a subset of the reference sub-fingerprints; and
comparing every thirty-second sub-fingerprint of the query fingerprint with sequential ones of the subset of the reference sub-fingerprints.
17. The method of claim 11 , wherein each thread of the plurality of threads stores the first predetermined number of lowest bit error rates.
18. The method of claim 14 , further including:
assigning each of the segments to a different server on a network; and
cause the different servers to determine the first bit error rate for the segments.
19. A non-transitory machine-readable storage medium comprising instructions that, when executed by one or more processors of a machine, cause the machine to at least:
obtain a query fingerprint including a plurality of sub-fingerprints;
divide a set of reference fingerprints into segments, each segment including a plurality of reference sub-fingerprints;
cause a plurality of threads to determine first bit error rates by performing, in parallel, one or more operations including determining one of the first bit error rates by comparing a portion of the plurality of sub-fingerprints of the query fingerprint with a portion of the plurality of reference sub-fingerprints of a segment;
identify a first predetermined number of lowest bit error rates based on the first bit error rates, each of the first predetermined number of lowest bit error rates corresponding to one of the set of reference fingerprints;
in response to identifying the first predetermined number of lowest bit error rates based on the first bit error rates, for each of the first predetermined number of lowest bit error rates, determine a second bit error rate by evaluating the query fingerprint against the corresponding one of the set of reference fingerprints; and
provide a predetermined number of response candidates based on the second bit error rate determined for each of the first predetermined number of lowest bit error rates.
20. The non-transitory machine-readable storage medium of claim 19 , wherein the instructions, when executed by the one or more processors of the machine, cause the machine to:
sub-sample the reference fingerprints by a first factor to determine a first set of the reference sub-fingerprints;
sub-sample the query fingerprint by the first factor to determine a second set of the sub-fingerprints of the query fingerprint;
determine the first predetermined number of lowest bit error rates based on a comparison of the first set and the second set to determine a third set of the reference fingerprints, the third set corresponding to one or more of the reference fingerprints associated with the first predetermined number of lowest bit error rates;
sub-sample one or more of the third set by a second factor to determine a fourth set of the reference sub-fingerprints, the second factor greater than the first factor;
sub-sample the query fingerprint by the second factor to determine a fifth set of the sub-fingerprints of the query fingerprint; and
determine the predetermined number of response candidates based on the comparison of the fourth set and the fifth set.