Signature representation of data having high dimensionality

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

setting an initial value of each vector element in the m vector elements to zero; and

for each vector element in the m vector elements:

accessing a plurality of key-value pairs sequentially, each key-value pair 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 by repeating, sequentially, for each respective key-value pair in the plurality of key-value pairs:

calculating a respective term of the plurality of terms based on the respective key-value pair from the plurality of key-value pairs by:

generating a hash 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 hash; and

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

adding the respective term calculated to the vector element being calculated,

wherein m<<n.

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

3. The method of claim 1 , 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 data received is a complete set of data.

5. The method claim 3 , wherein the data received is an incomplete set of data.

6. 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.

7. The method of claim 1 , wherein the plurality of key-value pairs includes at least two key-value pairs having the same key.

8. The method of claim 7 , 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.

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 of 1 , wherein the element identifier associated with the vector element being calculated is based on an index value of the vector element being calculated.

11. The method of claim 10 , wherein the hash is generated from concatenation of the element identifier associated with the vector element being calculated, and the key of the respective key-value pair.

12. The method of claim 11 , wherein the hash is generated based on the function:

hash(str( i )+str( K l ))

wherein: i is the element identifier associated with the vector element being calculated, K l is the key of the respective key-value pair, and the ‘+’ operator is a concatenation of strings.

13. 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.

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

a non-transitory computer-readable memory containing instructions; and

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

setting an initial value of each vector element in the m vector elements to zero; and

for each vector element in the m vector elements:

accessing a plurality of key-value pairs sequentially, each key-value pair 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 by repeating, sequentially, for each respective key-value pair in the plurality of key-value pairs:

calculating a respective term of the plurality of terms based on the respective key-value pair from the plurality of key-value pairs by:

generating a hash 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 hash; and

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

adding the respective term calculated to the vector element being calculated, wherein m<<n.

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

16. The computing device of claim 14 , 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.

17. The computing device of claim 16 , wherein the data received is a complete set of data.

18. The computing device of claim 16 , wherein the data received is an incomplete set of data.

19. The computing device of claim 16 , 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.

20. The computing device of claim 14 , wherein the plurality of key-value pairs includes at least two key-value pairs having the same key.

21. The computing device of claim 20 , 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.

22. The computing device of claim 14 , 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.

23. The computing device of claim of 14 , wherein the element identifier associated with the vector element being calculated is based on an index value of the vector element being calculated.

24. The computing device of claim 23 , wherein the hash is generated from concatenation of the element identifier associated with the vector element being calculated, and the key of the respective key-value pair.

25. The computing device of claim 24 , wherein the hash is generated based on the function:

hash(str( i )+str( K l ))

wherein: i is the element identifier associated with the vector element being calculated, K l is the key of the respective key-value pair, and the ‘+’ operator is a concatenation of strings.

26. The computing device of claim 14 , 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.

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:

setting an initial value of each vector element in the m vector elements to zero; and

for each vector element in the m vector elements:

accessing a plurality of key-value pairs sequentially, each key-value pair 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 by repeating, sequentially, for each respective key-value pair in the plurality of key-value pairs:

calculating a respective term of the plurality of terms based on the respective key-value pair from the plurality of key-value pairs by:

generating a hash 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 hash; and

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

adding the respective term calculated to the vector element being calculated,

wherein m<<n.