Signature representation of data with aliasing across synonyms
View Patent ↗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.
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.