GENERATING CORRELATION SCORES

• US 20150317281A1
• Filed: 04/30/2014
• Published: 11/05/2015
• Est. Priority Date: 04/30/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sharifi, Matthew, Roblek, Dominik
• Granted Patent: US 9,569,405 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78

Abstract

A computer-implemented method includes obtaining first and second binary vectors. For each of a plurality of vector locations in a first of j words in the first binary vector, the method includes shifting the binary values for the second binary vector so that a particular one of the binary values in the second binary vector is located at a vector location in a first of the k words in the second binary vector that matches the vector location in the first of j words in the first binary vector. For each of the j words in the first binary vector, the method includes aligning the second binary vector with the word in the first binary vector and determining a binary correlation score. A similarity of the first binary vector and the second binary vector can be determined based at least on one or more of the determined binary correlation scores.

Claims

1. A computer-implemented method, comprising:

obtaining a first binary vector of length X and a second binary vector of length Y, the first and second binary vectors each being segmented into words of length n, the first binary vector of length X being longer than the second binary vector of length Y, the first binary vector comprising respective binary values for a plurality of vector locations 0 through X−

1, the second binary vector comprising respective binary values for a plurality of vector locations 0 through Y−

1;

aligning the second binary vector in a first position with respect to the first binary vector so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector;

generating a binary correlation score for the first position of the second binary vector with respect to the first binary vector by performing respective binary operations between each binary value in the second binary vector in the first position and the aligned binary value in the first binary vector;

aligning the second binary vector in a second position with respect to the first binary vector, without shifting binary values of the second binary vector to different vector locations in the second binary vector, so that each of the binary values in the second binary vector aligns with a respective binary value in the first binary vector, the second position being offset by a multiple of n vector locations from the first position with respect to the first binary vector;

generating a binary correlation score for the second position of the second binary vector with respect to the first binary vector by performing respective binary operations between each binary value in the second binary vector in the second position and the aligned binary value in the first binary vector; and

determining whether the first binary vector is similar to the second binary vector based at least on one or more of the binary correlation scores.

2. The computer-implemented method of claim 1, wherein the second binary vector of length Y is a multiple of the word length n and each word in the second binary vector is filled with n binary values.

3. The computer-implemented method of claim 1, wherein:

aligning the second binary vector in the first position with respect to the first binary vector and generating the binary correlation score for the first position of the second binary vector comprises aligning the second binary vector and generating the binary correlation score without shifting binary values of the second binary vector to different vector locations in the second binary vector; and

aligning the second binary vector in the second position with respect to the first binary vector and generating the binary correlation score for the second position of the second binary vector comprises aligning the second binary vector and generating the binary correlation score without shifting binary values of the second binary vector to different vector locations in the second binary vector.

4. The computer-implemented method of claim 1, wherein:

the first binary vector is segmented into j words of length n;

the second binary vector is segmented into k words of length n;

aligning the second binary vector in the first position with respect to the first binary vector comprises aligning a first of the k words in the second binary vector with a first of the j words in the first binary vector; and

aligning the second binary vector in the second position with respect to the first binary vector comprises aligning the first of the k words in the second binary vector with a second of the j words in the first binary vector that is different than the first of the j words in the first binary vector.

5. The computer-implemented method of claim 4, further comprising, for each of a plurality of words selected from a group consisting of the j words in the first binary vector other than the first and second of the j words:

aligning the second binary vector in a particular position with respect to the first binary vector by aligning the first of the k words in the second binary vector with the respective word among the plurality of words in the first binary vector; and

generating a binary correlation score for the particular position of the second binary vector with respect to the first binary vector by performing respective binary operations between each binary value in the second binary vector in the particular position and the aligned binary value in the first binary vector.

6. The computer-implemented method of claim 5, wherein the plurality of words selected from the group consisting of the j words in the first binary vector other than the first and second of the j words comprises all j−

2 words in the first binary vector other than the first and second of the j words.

7. The computer-implemented method of claim 1, further comprising:

shifting the binary values of the second binary vector by one vector location to generate a first shifted second binary vector in which binary values in the first shifted second binary vector are offset from corresponding binary values in the second binary vector by one vector location; and

for each of at least some of the words in the first binary vector, aligning a first word of the first shifted second binary vector with the word in the first binary vector and generating a binary correlation score by performing respective binary operations between each binary value in the first shifted second binary vector and a respective aligned binary value in the first binary vector.

8. The computer-implemented method of claim 7, further comprising:

generating n−

2 additional shifted second binary vectors in which, for each m from 2 through n−

1, an mth one of the additional shifted second binary vectors has respective binary values that are offset from corresponding binary values in the second binary vector by m vector locations; and

generating binary correlation scores using the additional shifted second binary vectors by aligning each of the additional shifted second binary vectors in one or more positions with respect to the first binary vector and performing binary operations to generate a respective binary correlation score.

9. The computer-implemented method of claim 1, further comprising:

shifting the binary values of the first binary vector by a first number of vector locations to generate a first shifted first binary vector in which binary values in the first shifted first binary vector are offset from corresponding binary values in the first binary vector by the first number of vector locations; and

for each of at least some of the words in the first shifted first binary vector, aligning a first word of the second binary vector with the word in the first shifted first binary vector and generating a binary correlation score by performing respective binary operations between each binary value in the second binary vector and an aligned binary value in the first shifted first binary vector.

10. The computer-implemented method of claim 1, further comprising shifting the binary values of the first binary vector by one vector location at a time for a total of n−

1 times, and generating, after each shift of the first binary vector, one or more binary correlation scores based on the shifted first binary vector and the second binary vector.

11. The computer-implemented method of claim 1, further comprising determining a cross-correlation of the first binary vector and the second binary vector based on one or more of the binary correlation scores.

12. The computer-implemented method of claim 11, wherein determining whether the first binary vector is similar to the second binary vector comprises determining whether a value of the cross-correlation of the first binary vector and the second binary vector satisfies a threshold cross-correlation value.

13. The computer-implemented method of claim 1, further comprising using one or more of the binary correlation scores to determine whether an audio signal represented by the first binary vector includes an echo of an audio signal represented by the second binary vector.

14. The computer-implemented method of claim 1, wherein the binary values in the first binary vector and the second binary vector each represent changes among consecutive digitized samples in one or more sets of data, wherein the first binary vector and the second binary vector each comprises binary values consisting of 0 and 1, wherein a binary value of 1 indicates an increase from a first sample value to a next sample value in the one or more sets of data, wherein a binary value of 0 indicates a decrease from a first sample value to a next sample value in the one or more sets of data.

15. The computer-implemented method of claim 1, wherein:

the first binary vector and the second binary vector each comprises binary values consisting of 0 and 1; and

performing respective binary operations to generate a binary correlation score for the first position or the second position of the second binary vector with respect to the first binary vector comprises performing an XOR operation between each binary value in the second binary vector in the first or second position, respectively, and the aligned binary value in the first binary vector.

16. A computer-implemented method, comprising:

obtaining a first binary vector of length X and a second binary vector of length Y, the first binary vector of length X being longer than the second binary vector of length Y, the first binary vector being segmented into j words of length n, the second binary vector being segmented into k words of length n, the first binary vector comprising respective binary values for a plurality of vector locations 0 through X−

1, the second binary vector comprising respective binary values for a plurality of vector locations 0 through Y−

1;

for each of a plurality of vector locations in a first of the j words in the first binary vector;

shifting the binary values for the second binary vector so that a particular one of the binary values in the second binary vector is located at a vector location in a first of the k words in the second binary vector that matches the vector location in the first of the j words in the first binary vector, and

for each of the j words in the first binary vector, aligning the second binary vector with the word in the first binary vector and determining a binary correlation score; and

determining a similarity of the first binary vector and the second binary vector based at least on one or more of the determined binary correlation scores.

17. The computer-implemented method of claim 16, wherein the plurality of vector locations in the first of the j words in the first binary vector consists of n−

1 different vector locations that excludes a first vector location in the first of the j words in the first binary vector;

the method further comprising;

identifying that the particular one of the binary values in the second binary vector is located at a vector location in the first of the k words in the second binary vector that matches the first vector location in the first of the j words in the first binary vector; and

for each of the j words in the first binary vector and while the particular one of the binary values in the second binary vector is located at the vector location in the first of the k words in the second binary vector that matches the first vector location in the first of the j words in the first binary vector, aligning the second binary vector with the word in the first binary vector and determining a binary correlation score.

18. The computer-implemented method of claim 16, further comprising using one or more of the binary correlation scores to determine whether an audio signal represented by the first binary vector includes an echo of an audio signal represented by the second binary vector.

19. One or more computer-readable storage devices including instructions that, when executed by one or more computer processors, cause the one or more computer processors to perform operations comprising:

obtaining a first binary vector of length X and a second binary vector of length Y, the first binary vector of length X being longer than the second binary vector of length Y, the first binary vector being segmented into j words of length n, the second binary vector being segmented into k words of length n, the first binary vector comprising respective binary values for a plurality of vector locations 0 through X−

1, the second binary vector comprising respective binary values for a plurality of vector locations 0 through Y−

1;

for each of a plurality of vector locations in a first of the j words in the first binary vector;

shifting the binary values for the second binary vector so that a particular one of the binary values in the second binary vector is located at a vector location in a first of the k words in the second binary vector that matches the vector location in the first of the j words in the first binary vector, and

for each of the j words in the first binary vector, aligning the second binary vector with the word in the first binary vector and determining a binary correlation score; and

determining a similarity of the first binary vector and the second binary vector based at least on one or more of the determined binary correlation scores.

20. The one or more computer-readable storage devices of claim 19, wherein:

the plurality of vector locations in the first of the j words in the first binary vector consists of n−

1 different vector locations that excludes a first vector location in the first of the j words in the first binary vector; and

the operations further comprise;

identifying that the particular one of the binary values in the second binary vector is located at a vector location in the first of the k words in the second binary vector that matches the first vector location in the first of the j words in the first binary vector; and

for each of the j words in the first binary vector and while the particular one of the binary values in the second binary vector is located at the vector location in the first of the k words in the second binary vector that matches the first vector location in the first of the j words in the first binary vector, aligning the second binary vector with the word in the first binary vector and determining a binary correlation score.