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 computer-implemented method comprising:
obtaining a query fingerprint comprising a plurality of query sub-fingerprints;
providing the query fingerprint to a plurality of devices, wherein each device in the plurality of devices is associated with a corresponding plurality of segments of reference fingerprints divided from a set of reference fingerprints, wherein each segment includes a plurality of reference sub-fingerprints, wherein each device in the plurality of devices creates one or more thread groups, wherein each thread in the one or more thread groups accesses a portion of an associated segment of reference fingerprints and compares a portion of the query sub-fingerprints with a portion of the reference sub-fingerprints in the accessed portion of the associated segment of reference fingerprints to determine a set of first bit error rates;
identifying a predetermined number of lowest bit error rates based on aggregating the set of first bit error rates determined by each thread in the one or more thread groups, wherein each of the predetermined number of lowest bit error rates corresponds to a reference fingerprint of the set of reference fingerprints;
in response to identifying the predetermined number of lowest bit error rates, for each reference fingerprint of the reference fingerprints corresponding to the predetermined number of lowest bit error rates, determining a second bit error rate by comparing the query fingerprint with the reference fingerprint;
in response to determining the second bit error rate for one or more of the reference fingerprints corresponding to the predetermined number of lowest bit error rates, determining at least one response candidate based on the second bit error rates; and
providing the at least one response candidate in a response to a query including the query fingerprint.
2 . The computer-implemented method of claim 1 , further comprising down-sampling the segments of reference fingerprints at a first down-sampling rate for a first comparison pass.
3 . The computer-implemented method of claim 1 , further comprising storing the predetermined number of lowest bit error rates.
4 . The computer-implemented method of claim 1 , wherein each segment of reference fingerprints is divided into one or more chunks, wherein each thread group is associated with a chunk of the one or more chunks.
5 . The computer-implemented method of claim 1 , wherein each thread group forms a warp.
6 . The computer-implemented method of claim 2 , further comprising down-sampling the segments of reference fingerprints at a second down-sampling rate for a second comparison pass.
7 . The computer-implemented method of claim 6 , wherein the first down-sampling rate is greater than the second down-sampling rate.
8 . A tangible, non-transitory computer readable medium comprising instructions that, when executed, cause at least one processor to perform a set of operations comprising:
obtaining a query fingerprint comprising a plurality of query sub-fingerprints;
providing the query fingerprint to a plurality of devices, wherein each device in the plurality of devices is associated with a corresponding plurality of segments of reference fingerprints divided from a set of reference fingerprints, wherein each segment includes a plurality of reference sub-fingerprints, wherein each device in the plurality of devices creates one or more thread groups, wherein each thread in the one or more thread groups accesses a portion of an associated segment of reference fingerprints and compares a portion of the query sub-fingerprints with a portion of the reference sub-fingerprints in the accessed portion of the associated segment of reference fingerprints to determine a set of first bit error rates; identifying a predetermined number of lowest bit error rates based on aggregating the set of first bit error rates determined by each thread in the one or more thread groups, wherein each of the predetermined number of lowest bit error rates corresponds to a reference fingerprint of the set of reference fingerprints;
in response to identifying the predetermined number of lowest bit error rates, for each reference fingerprint of the reference fingerprints corresponding to the predetermined number of lowest bit error rates, determining a second bit error rate by comparing the query fingerprint with the reference fingerprint;
in response to determining the second bit error rate for one or more of the reference fingerprints corresponding to the predetermined number of lowest bit error rates, determining at least one response candidate based on the second bit error rates; and
providing the at least one response candidate in a response to a query including the query fingerprint.
9 . The tangible, non-transitory computer readable medium of claim 8 , wherein the set of operations further comprises down-sampling the segments of reference fingerprints at a first down-sampling rate for a first comparison pass.
10 . The tangible, non-transitory computer readable medium of claim 8 , f wherein the set of operations further comprises storing the predetermined number of lowest bit error rates.
11 . The tangible, non-transitory computer readable medium of claim 8 , wherein each segment of reference fingerprints is divided into one or more chunks, wherein each thread group is associated with a chunk of the one or more chunks.
12 . The tangible, non-transitory computer readable medium of claim 8 , wherein each thread group forms a warp.
13 . The tangible, non-transitory computer readable medium of claim 9 , wherein the set of operations further comprises down-sampling the segments of reference fingerprints at a second down-sampling rate for a second comparison pass.
14 . The tangible, non-transitory computer readable medium of claim 13 , wherein the first down-sampling rate is greater than the second down-sampling rate.
15 . A computing device comprising:
at least one processors; and
tangible, non-transitory computer readable medium comprising instructions that, when executed, cause the at least one processor to perform a set of operations comprising:
obtaining a query fingerprint comprising a plurality of query sub-fingerprints;
providing the query fingerprint to a plurality of devices, wherein each device in the plurality of devices is associated with a corresponding plurality of segments of reference fingerprints divided from a set of reference fingerprints, wherein each segment includes a plurality of reference sub-fingerprints, wherein each device in the plurality of devices creates one or more thread groups, wherein each thread in the one or more thread groups accesses a portion of an associated segment of reference fingerprints and compares a portion of the query sub-fingerprints with a portion of the reference sub-fingerprints in the accessed portion of the associated segment of reference fingerprints to determine a set of first bit error rates;
identifying a predetermined number of lowest bit error rates based on aggregating the set of first bit error rates determined by each thread in the one or more thread groups, wherein each of the predetermined number of lowest bit error rates corresponds to a reference fingerprint of the set of reference fingerprints;
in response to identifying the predetermined number of lowest bit error rates, for each reference fingerprint of the reference fingerprints corresponding to the predetermined number of lowest bit error rates, determining a second bit error rate by comparing the query fingerprint with the reference fingerprint;
in response to determining the second bit error rate for one or more of the reference fingerprints corresponding to the predetermined number of lowest bit error rates, determining at least one response candidate based on the second bit error rates; and
providing the at least one response candidate in a response to a query including the query fingerprint.
16 . The computing device of claim 15 , wherein the set of operations further comprises down-sampling the segments of reference fingerprints at a first down-sampling rate for a first comparison pass.
17 . The computing device of claim 15 , wherein each segment of reference fingerprints is divided into one or more chunks, wherein each thread group is associated with a chunk of the one or more chunks.
18 . The computing device of claim 15 , wherein each thread group forms a warp.
19 . The computing device of claim 16 , wherein the set of operations further comprises down-sampling the segments of reference fingerprints at a second down-sampling rate for a second comparison pass.
20 . The computing device of claim 19 , wherein the first down-sampling rate is greater than the second down-sampling rate.