Patent ID: 8447032

Claim:
A computer-implemented method for generating a signature representing an input bit vector, wherein each bit of the input bit vector comprises either a first predefined value or a second predefined value, the second predefined value different than the first predefined value, the computer-implemented method comprising: applying a primary permutation to the input bit vector to generate a primary permuted input bit vector; generating a primary min-hash value based on a bit location of a sequentially first occurring bit in the primary permuted input bit vector that has said first predefined value; comparing, by a computing device, the primary min-hash value to a threshold value; responsive to the primary min-hash value being less than the threshold value, applying a secondary permutation to the input bit vector to generate a secondary permuted bit vector, and generating a secondary min-hash value based on a bit location of a sequentially first occurring bit in the secondary permuted input bit vector that has said first predefined value, wherein the secondary permutation is different than the primary permutation; determining one or more signature values based on at least one of the primary min-hash value and the secondary min-hash value; and storing the one or more signature values to a non-transitory computer readable storage medium as elements of the signature.