Signature representation of data having high dimensionality

• US 8,908,978 B2
• Filed: 06/06/2014
• Issued: 12/09/2014
• 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
• Primary Examiner(s): Liew, Alex
• Application Number:
  US14/298,285
• Publication Number:
  US 20140286582A1
• Time in Patent Office: 186 Days
• Field of Search: 382181-231, 382232-253
• US Class Current: 382/232
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H03M 7/3062 Compressive sampling or sensing
• CPC Class Codes: H04L 27/0006 Assessment of spectral gaps suitable for allocating digitally modulated signals, e.g. for carrier allocation in cognitive radio for spectrum sharing between different networks H04W16/14

Abstract

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.

Claims

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.