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. An apparatus comprising:
at least one memory;
machine readable instructions; and
processor circuitry to at least one of instantiate or execute the machine readable instructions to:
divide reference fingerprints into a plurality of reference fingerprint segments, including a first reference fingerprint segment and a second reference fingerprint segment;
assign the first reference fingerprint segment to a first device of a plurality of devices and assign the second reference fingerprint segment to a second device of a plurality of devices, the first reference fingerprint segment including a first plurality of reference sub-fingerprints and the second reference fingerprint segment including a second plurality of reference sub-fingerprints;
provide a query fingerprint to the first and second devices;
cause a first plurality of groups of threads running on the first device to compare the query fingerprint to the first plurality of reference sub-fingerprints and cause a second plurality of groups of threads running on the second device to compare the query fingerprint to the second plurality of reference sub-fingerprints at a first down-sampling rate, wherein comparing the query fingerprint to each reference sub-fingerprint produces bit error rates;
aggregate a lowest bit error rate produced across the first plurality of groups of threads and the second plurality of groups of threads;
based on the aggregated lowest bit error rate, determine a plurality of candidate reference sub-fingerprints from the first plurality of reference sub-fingerprints and second plurality of reference sub-fingerprints; and
cause at least one of the first plurality of groups of threads running on the first device and the second plurality of groups of threads running on the second device to compare the query fingerprint to the plurality of candidate reference sub-fingerprints at a second down-sampling rate.
2. The apparatus of claim 1 , wherein the first down-sampling rate is greater than the second down-sampling rate.
3. The apparatus of claim 1 , wherein the processor circuitry is to cause at least a first thread of the first plurality of groups of threads to toggle ones of bits of at least one reference sub-fingerprint of the first plurality of reference sub-fingerprints in a plurality of comparison passes.
4. The apparatus of claim 1 , wherein ones of the plurality of reference sub-fingerprints include partially overlapping periods of time with other ones of the first plurality of reference sub-fingerprints.
5. The apparatus of claim 1 , wherein the processor circuitry is to:
provide a bit mask for a first reference sub-fingerprint of the first plurality of reference sub-fingerprints, the bit mask to indicate ones of weak bits with lower confidence values in the first reference sub-fingerprint; and
cause at least a first thread of the first plurality of groups of threads to compare a plurality of permutations of bit values of the ones of weak bits in the first reference sub-fingerprint to at least a portion of the query fingerprint.
6. The apparatus of claim 1 , wherein the processor circuitry is to cause at least a first thread of the first plurality of groups of threads to compare at least two reference sub-fingerprints of the first plurality of reference sub-fingerprints to at least a portion of the query fingerprint, wherein the at least two reference sub-fingerprints are non-contiguous portions of the first reference fingerprint segment.
7. The apparatus of claim 2 , wherein the processor circuitry is to:
divide the query fingerprint into a plurality of query sub-fingerprints; and
cause at least the first plurality of groups of threads to compare ones of the first plurality of reference sub-fingerprints to ones of the plurality of query sub-fingerprints.
8. A non-transitory machine readable storage medium comprising instructions that, when executed, cause processor circuitry to at least:
divide reference fingerprints into a plurality of reference fingerprint segments, including a first reference fingerprint segment and a second reference fingerprint segment;
assign the first reference fingerprint segment to a first device of a plurality of devices and assign the second reference fingerprint segment to a second device of a plurality of devices, the first reference fingerprint segment including a first plurality of reference sub-fingerprints and the second reference fingerprint segment including a second plurality of reference sub-fingerprints;
provide a query fingerprint to the first and second devices;
cause a first plurality of groups of threads running on the first device to compare the query fingerprint to the first plurality of reference sub-fingerprints and cause a second plurality of groups of threads running on the second device to compare the query fingerprint to the second plurality of reference sub-fingerprints at a first down-sampling rate, wherein comparing the query fingerprint to each reference sub-fingerprint produces bit error rates;
aggregate a lowest bit error rate produced across the first plurality of groups of threads and the second plurality of groups of threads;
based on the aggregated lowest bit error rate, determine a plurality of candidate reference sub-fingerprints from the first plurality of reference sub-fungerprints and second plurality of reference sub-fingerprints; and
cause at least one of the first plurality of groups of threads running on the first device and the second plurality of groups of threads running on the second device to compare the query fingerprint to the plurality of candidate reference sub-fingerprints at a second down-sampling rate.
9. The non-transitory machine readable storage medium of claim 8 , wherein the first down-sampling rate is greater than the second down-sampling rate.
10. The non-transitory machine readable storage medium of claim 8 , wherein instructions cause the processor circuitry to at least:
cause at least a first thread of the first plurality of groups of threads to toggle ones of bits of at least one reference sub-fingerprint of the first plurality of reference sub-fingerprints in a plurality of comparison passes.
11. The non-transitory machine readable storage medium of claim 8 , wherein ones of the plurality of reference sub-fingerprints include partially overlapping periods of time with other ones of the first plurality of reference sub-fingerprints.
12. The non-transitory machine readable storage medium of claim 8 , wherein instructions cause the processor circuitry to at least:
provide a bit mask for a first reference sub-fingerprint of the first plurality of reference sub-fingerprints, the bit mask to indicate ones of weak bits with lower confidence values in the first reference sub-fingerprint; and
cause at least a first thread of the first plurality of groups of threads to compare a plurality of permutations of bit values of the ones of weak bits in the first reference sub-fingerprint to at least a portion of the query fingerprint.
13. The non-transitory machine readable storage medium of claim 8 , wherein instructions cause the processor circuitry to at least:
cause at least a first thread of the first plurality of groups of threads to compare at least two reference sub-fingerprints of the first plurality of reference sub-fingerprints to at least a portion of the query fingerprint, wherein the at least two reference sub-fingerprints are non-contiguous portions of the first reference fingerprint segment.
14. The non-transitory machine readable storage medium of claim 9 , wherein instructions cause the processor circuitry to at least:
divide the query fingerprint into a plurality of query sub-fingerprints; and
cause at least the first plurality of groups of threads to compare ones of the first plurality of reference sub-fingerprints to ones of the plurality of query sub-fingerprints.
15. A method, comprising:
dividing reference fingerprints into a plurality of reference fingerprint segments, including a first reference fingerprint segment and a second reference fingerprint segment;
assigning the first reference fingerprint segment to a first device of a plurality of devices and assign the second reference fingerprint segment to a second device of a plurality of devices, the first reference fingerprint segment including a first plurality of reference sub-fingerprints and the second reference fingerprint segment including a second plurality of reference sub-fingerprints;
providing a query fingerprint to the first and second devices;
causing a first plurality of groups of threads running on the first device to compare the query fingerprint to the first plurality of reference sub-fingerprints and cause a second plurality of groups of threads running on the second device to compare the query fingerprint to the second plurality of reference sub-fingerprints at a first down-sampling rate, wherein comparing the query fingerprint to each reference sub-fingerprint produces bit error rates;
aggregating a lowest bit error rate produced across the first plurality of groups of threads and the second plurality of groups of threads;
based on the aggregated lowest bit error rate, determining a plurality of candidate reference sub-fingerprints from the first plurality of reference sub-fingerprints and second plurality of reference sub-fingerprints; and
causing at least one of the first plurality of groups of threads running on the first device and the second plurality of groups of threads running on the second device to compare the query fingerprint to the plurality of candidate reference sub-fingerprints at a second down-sampling rate.
16. The method of claim 15 , wherein the first down-sampling rate is greater than the second down-sampling rate.
17. The method of claim 15 , including:
causing at least a first thread of the first plurality of groups of threads to toggle ones of bits of at least one reference sub-fingerprint of the first plurality of reference sub-fingerprints in a plurality of comparison passes.
18. The method of claim 15 , wherein ones of the plurality of reference sub-fingerprints include partially overlapping periods of time with other ones of the first plurality of reference sub-fingerprints.
19. The method of claim 15 , including:
providing a bit mask for a first reference sub-fingerprint of the first plurality of reference sub-fingerprints, the bit mask to indicate ones of weak bits with lower confidence values in the first reference sub-fingerprint; and
causing at least a first thread of the first plurality of groups of threads to compare a plurality of permutations of bit values of the ones of weak bits in the first reference sub-fingerprint to at least a portion of the query fingerprint.
20. The method of claim 16 , including:
dividing the query fingerprint into a plurality of query sub-fingerprints; and
causing at least the first plurality of groups of threads to compare ones of the first plurality of reference sub-fingerprints to ones of the plurality of query sub-fingerprints.