Signature representation of data with aliasing across synonyms

• US 9,069,634 B2
• Filed: 03/09/2012
• Issued: 06/30/2015
• Est. Priority Date: 03/09/2012
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Oka, Anand Ravindra, Snow, Christopher Harris, Simmons, Sean Bartholomew, Naddafzadeh Shirazi, Ghasem
• Primary Examiner(s): Yaary, Michael D
• Application Number:
  US13/416,589
• Publication Number:
  US 20130238681A1
• Time in Patent Office: 1,208 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: H03M 7/3062 Compressive sampling or sensing

Abstract

A system and method for generating an m-dimensional signature vector with aliasing across synonyms in a computing device is provided. Data representable by a plurality of key-value pairs, each comprising a unique identifier and an associated non-zero value of n-dimensional data is received at the computing device. Elements of the m-dimensional aliased signature vector are generated using synonym information of keys from the plurality of key-value pairs.

Claims

1. A method for generating, in a computing device, an m-dimensional aliased signature vector comprising m vector elements, the method comprising:

accessing a plurality of key-value pairs, each comprising a respective key, corresponding to one of n unique identifiers, and a non-zero value, at least one of the keys being associated with one or more synonymous unique identifiers from the n unique identifiers; and

calculating each vector element based on a summation of a plurality of terms, each term calculated from a respective key-value pair, when the key of the respective key-value pair is associated one or more synonymous unique identifiers, the term calculated by adding one or more sub-terms, each calculated from a respective synonymous unique identifier of the one or more synonymous unique identifiers associated with the key of the respective key-value pair by;

generating a synonym seed based on the respective synonymous unique identifier and the element identifier associated with the vector element being calculated;

generating a synonym pseudo-random number from the generated synonym seed; and

multiplying the synonym pseudo-random number by the value of the respective key-value pair,

wherein m>

>

n.

2. The method of claim 1 wherein when the key of the key-value pair is not associated with one or more synonymous unique identifiers, the term calculated by:

generating a seed based on the key of the respective key-value pair and an element identifier associated with the vector element being calculated;

generating a pseudo-random number from the generated seed; and

multiplying the pseudo-random number by the value of the respective key-value pair.

3. The method of claim 1, wherein synonym information associates a plurality of synonymous unique identifiers together, and a key of the key-value pairs is associated with synonymous unique identifiers if the key matches one of the synonymous unique identifiers.

4. The method of claim 3, wherein the synonym information is stored as one or more of:

a synonym matrix;

a plurality of tuples of synonymous unique identifiers;

or

a list of lists of synonymous unique identifiers.

5. The method of claim 3, wherein the synonym information is a formula used to determine a similarity between two or more synonymous unique identifiers.

6. The method of claim 3, wherein the synonym information further associates with the synonymous unique identifiers, a synonym weighting value indicating a degree of similarity between synonymous unique identifiers.

7. The method of claim 6, wherein when the key of the respective key-value pair is associated with one or more synonymous unique identifiers, the term calculated by further:

normalizing the term by dividing the term by the sum of the synonym weighting values associated with the synonymous unique identifiers associated with the key of the key-value pair.

8. The method of claim 1, wherein when the key of the respective key-value pair is associated with one or more synonymous unique identifiers, the term calculated by further:

normalizing the term by dividing by the number of synonymous unique identifiers associated with the key of the key-value pair.

9. The method of claim 1, wherein no two key-value pairs have the same key.

10. The method of claim 1, wherein generating each of the elements further comprises weighting each of the terms based on a weighting value for the key associated with the respective term.

11. The method of claim 1, wherein the key-value pairs include at least two key-value pairs having the same key.

12. The method of claim 1, wherein the signature is computed incrementally in a single pass, by progressively processing key-value pairs until it is fully consumed.

13. The method of claim 1, further comprising:

storing the m-dimensional signature vector in memory; and

comparing the m-dimensional signature vector to one or more previously generated m-dimensional signature vectors.

14. A computing device for generating an m-dimensional aliased signature vector, the device comprising:

a memory containing instructions; and

a processor for executing instructions, the instructions when executed by the processor configuring the device to provide functionality for;

accessing a plurality of key-value pairs, each comprising a respective key, corresponding to one of n unique identifiers, and a non-zero value, at least one of the keys being associated with one or more synonymous unique identifiers from the n unique identifiers; and

calculating each vector element based on a summation of a plurality of terms, each term calculated from a respective key-value pair, when the key of the respective key-value pair is associated one or more synonymous unique identifiers, the term calculated by adding one or more sub-terms, each calculated from a respective synonymous unique identifier of the one or more synonymous unique identifiers associated with the key of the respective key-value pair by;

generating a synonym seed based on the respective synonymous unique identifier and the element identifier associated with the vector element being calculated;

generating a synonym pseudo-random number from the generated synonym seed; and

multiplying the synonym pseudo-random number by the value of the respective key-value pair,

wherein m>

>

n.

15. The computing device of claim 14, wherein when the key of the key-value pair is not associated with one or more synonymous unique identifiers, the term calculated by:

generating a seed based on the key of the respective key-value pair and an element identifier associated with the vector element being calculated;

generating a pseudo-random number from the generated seed; and

multiplying the pseudo-random number by the value of the respective key-value pair.

16. The computing device of claim 14, wherein synonym information associates a plurality of synonymous unique identifiers together, and a key of the key-value pairs is associated with synonymous unique identifiers if the key matches one of the synonymous unique identifiers.

17. The computing device of claim 16, wherein the synonym information is stored as one or more of:

a synonym matrix;

a plurality of tuples of synonymous unique identifiers;

or

a list of lists of synonymous unique identifiers.

18. The computing device of claim 17, wherein the synonym information is a formula used to determine a similarity between two or more synonymous unique identifiers.

19. The computing device of claim 17, wherein the synonym information further associates with the synonymous unique identifiers, a synonym weighting value indicating a degree of similarity between synonymous unique identifiers.

20. The computing device of claim 19, wherein when the key of the respective key-value pair is associated with one or more synonymous unique identifiers, the term calculated by further:

normalizing the term by dividing the term by the sum of the synonym weighting values associated with the synonymous unique identifiers associated with the key of the key-value pair.

21. The computing device of claim 14, wherein when the key of the respective key-value pair is associated with one or more synonymous unique identifiers, the term calculated by further:

normalizing the term by dividing by the number of synonymous unique identifiers associated with the key of the key-value pair.

22. The computing device of claim 14, wherein no two key-value pairs have the same key.

23. The computing device of claim 14, wherein generating each of the elements further comprises weighting each of the terms based on a weighting value for the key associated with the respective term.

24. The computing device of claim 14, wherein the key-value pairs include at least two key-value pairs having the same key.

25. The computing device of claim 14, wherein the signature is computed incrementally in a single pass, by progressively processing key-value pairs until it is fully consumed.

26. The computing device of claims 14, further comprising:

storing the m-dimensional signature vector in memory; and

comparing the m-dimensional signature vector to one or more previously generated m-dimensional signature vectors.

27. A non-transitory computer readable memory containing instructions for generating an m-dimensional signature vector comprising m vector elements, the instructions which when executed by a processor perform the method of:

accessing a plurality of key-value pairs, each comprising a respective key, corresponding to one of n unique identifiers, and a non-zero value, at least one of the keys being associated with one or more synonymous unique identifiers from the n unique identifiers; and

calculating each vector element based on a summation of a plurality of terms, each term calculated from a respective key-value pair, when the key of the respective key-value pair is associated one or more synonymous unique identifiers, the term calculated by adding one or more sub-terms, each calculated from a respective synonymous unique identifier of the one or more synonymous unique identifiers associated with the key of the respective key-value pair by;

generating a synonym seed based on the respective synonymous unique identifier and the element identifier associated with the vector element being calculated;

generating a synonym pseudo-random number from the generated synonym seed; and

multiplying the synonym pseudo-random number by the value of the respective key-value pair,

wherein m>

>

n.