Signature representation of data having high dimensionality
A system and method for generating an m-dimensional signature vector in a computing device is provided. The signature vector may be generated from a plurality of key-value pairs, each comprising a unique identifier and an associated non-zero value. Each element of the m-dimensional signature vector is calculated based on a summation of a plurality of terms. Each of the terms is calculated from a respective key-value pair 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, wherein m<<n.
1. A method for generating, in a computing device, an m-dimensional 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; and
calculating each vector element based on a summation of a plurality of terms, each term calculated from a respective key-value pair 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,
wherein m<<n.
2. The method of claim 1 , wherein no two key-value pairs have the same key.
3. The method of claim 2 , wherein accessing the plurality of key-value pairs further comprises:
receiving data; and
determining the plurality of key-value pairs based on the received data.
4. The method of claim 3 , wherein the received data comprises text data and wherein determining the plurality of key-value pairs from the received text data comprises:
parsing the text data into a plurality of tokens; and
determining a frequency of occurrence of each unique token in the plurality of tokens parsed from the text data,
wherein, for each key-value pair, its key corresponds to a unique token, and its non-zero value is the determined frequency of occurrence of the unique token.
5. The method of claim 1 , wherein the plurality of key-value pairs includes at least two key-value pairs having the same key.
6. The method of claim 5 , further comprising:
receiving text data; and
parsing the text data into a plurality of tokens,
wherein the respective key of each key-value pair corresponds to a respective token of the plurality of parsed tokens, and the respective non-zero value of that key-value pair is 1.
7. The method of claim 6 , wherein a term in the summation of terms is calculated once a respective token is parsed from the text data file.
8. The method of claim 1 , wherein calculating each vector element further comprises:
setting an initial value of that vector element to zero; and
repeating for each key-value pair of the set of key-value pairs:
adding the respective term calculated from that key-value pair.
9. The method of claim 1 , wherein, for at least one term of the summation for at least one vector element, calculating that term further comprises multiplying the product of the respective pseudo-random number and the value of the respective key-value pair by a weighting value.
10. The method of claim 1 , further comprising:
taking a sign of each vector element to generate a binary-valued m-dimensional signature vector.
11. The method of claim 1 , further comprising:
storing the m-dimensional signature vector in memory; and
transmitting the m-dimensional signature vector to a remote device for comparison to one or more previously generated m-dimensional signature vectors.
12. 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.
13. The method of claim 12 , wherein comparing the m-dimensional signature vector to one or more previously generated m-dimensional signature vectors is performed by a method selected from the group consisting of: an inner product between two m-dimensional signature vectors, Euclidean distance between the two m-dimensional signature vectors, and a vantage point tree method.
14. The method of claim 1 , wherein for each key-value pair, its key comprises a radio frequency (RF) transmitter address, and its value comprises a received signal strength indicator associated with the address.
15. A computing device for generating an m-dimensional signature vector 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; and
calculating each vector element based on a summation of a plurality of terms, each term calculated from a respective key-value pair 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,
wherein m<<n.
16. The computing device of claim 15 , wherein no two key-value pairs have the same key.
17. The computing device of claim 16 , wherein the functionality for accessing the plurality of key-value pairs further comprises functionality for:
receiving data; and
determining the plurality of key-value pairs based on the received data.
18. The computing device of claim 17 , wherein the received data comprises text data and wherein the functionality for determining the plurality of key-value pairs from the received text data comprises functionality for:
parsing the text data into a plurality of tokens; and
determining a frequency of occurrence of each unique token in the plurality of tokens parsed from the text data,
wherein, for each key-value pair, its key corresponds to a unique token, and its non-zero value is the determined frequency of occurrence of the unique token.
19. The computing device of claim 15 , wherein the plurality of key-value pairs includes at least two key-value pairs having the same key.
20. The computing device of claim 19 , wherein the instructions executed by the processor further configure the device to provide functionality for:
receiving text data and
parsing the text data into a plurality of tokens,
wherein the respective key of each key-value pair corresponds to a respective token of the plurality of parsed tokens, and the respective non-zero value of that key-value pair is 1.
21. The computing device of claim 20 , wherein a term in the summation of terms is calculated once a respective token is parsed from the text data file.
22. The computing device of claim 15 , wherein the functionality for calculating each vector element further comprises functionality for:
setting an initial value of that vector element to zero; and
repeating for each key-value pair of the set of key-value pairs:
adding the respective term calculated from that key-value pair.
23. The computing device of claim 15 , wherein, for at least one term of the summation for at least one vector element, calculating that term further comprises multiplying the product of the respective pseudo-random number and the value of the respective key-value pair by a weighting value.
24. The computing device of claim 15 , wherein the instructions executed by the processor further configure the device to provide functionality for:
taking a sign of each vector element to generate a binary-valued m-dimensional signature vector.
25. The computing device of claim 15 , wherein the instructions executed by the processor further configure the device to provide functionality for:
storing the m-dimensional signature vector in memory; and
transmitting the m-dimensional signature vector to a remote device for comparison to one or more previously generated m-dimensional signature vectors.
26. The computing device of claim 15 , wherein the instructions executed by the processor further configure the device to provide functionality for 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. The computing device of claim 26 , wherein comparing the m-dimensional signature vector to one or more previously generated m-dimensional signature vectors is performed by a computing device selected from the group consisting of: an inner product between two m-dimensional signature vectors, Euclidean distance between the two m-dimensional signature vectors, and a vantage point tree computing device.
28. The computing device of claim 15 , wherein for each key-value pair, its key comprises a radio frequency (RF) transmitter address, and its value comprises a received signal strength indicator associated with the address.
29. 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; and
calculating each vector element based on a summation of a plurality of terms, each term calculated from a respective key-value pair 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,
wherein m <<n.