Location estimation system, method and program

• US 8,405,551 B2
• Filed: 02/10/2012
• Issued: 03/26/2013
• Est. Priority Date: 10/25/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hido, Shohei, Ide, Tsuyoshi, Kashima, Hisashi, Suzuki, Shoko, Tajima, Akira, Takahashi, Rikiya, Takahashi, Toshihiro, Tsuboi, Yuta
• Primary Examiner(s): Keith, Jack W
• Assistant Examiner(s): McGue, Frank J
• Application Number:
  US13/370,457
• Publication Number:
  US 20120143814A1
• Time in Patent Office: 410 Days
• Field of Search: 342/451, 342/417
• US Class Current: 342/451
• CPC Class Codes: G01S 5/02521 using a radio-map

Abstract

Location estimation systems, methods, and non-transitory computer program products. The system includes: storage means provided in the computer, means for storing the vector datasets in the storage means of the computer, means for calculating the similarity between the vector dataset without any location label and each neighboring vector dataset with a location label, by using any one of a q-norm where 0≦q≦1 and an exponential attenuation function, and means for estimating the location label of the vector data without any location label from the calculated similarities.

Claims

1. A system for estimating a location label of a vector dataset without any location label from a plurality of vector datasets respectively with location labels using a computer, the system comprising:

storage means provided in the computer;

means for storing the vector datasets in the storage means of the computer;

means for calculating a temporal and spatial similarity between the vector dataset without any location label and each neighboring vector dataset with a location label, by using a q-norm wherein 0<

q<

1 and an exponential attenuation function; and

means for estimating the location label of the vector data without any location label by using the larger of the temporal and spatial calculated similarities,

wherein one of the i) the q-norm where 0<

q<

1 and ii) the exponential attenuation function is used to determine the temporal similarity and the other is used to used to determine the spatial similarity.

2. The system according to claim 1, wherein the similarity calculated using the q-norm is calculated by means of the following expression,

W_X^(i,j)=exp(−

∥

X⁽ⁱ⁾−

X^(j)∥

_q^q),

where X(⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively, and

3. The system according to claim 1, wherein the similarity calculated using the exponential attenuation function is calculated by means of the following expression,

4. The system according to claim 1, wherein the similarity calculated using the exponential attenuation function is calculated by means of the following expression,

5. A computer-implemented method for estimating a location label of a vector dataset without any location label from a plurality of vector datasets respectively with location labels using a computer device, the method comprising:

storing the vector datasets;

calculating a temporal and spatial similarity between the vector dataset without any location label and each neighboring vector dataset with a location label, by using a q-norm wherein 0<

q<

1 and an exponential attenuation function; and

estimating the location label of the vector data without any location label by using the larger of the temporal and spatial calculated similarities,

wherein one of i) the q-norm where 0<

q<

1 and ii) the exponential attenuation function is used to determine the temporal similarity and the other is used to used to determine the spatial similarity,

wherein at least one step of the method is carried out on the computer device.

6. The method according to claim 5, wherein the similarity calculated using the q-norm is calculated by using the following expression,

W_X^(i,j)=exp(−

∥

X⁽ⁱ⁾−

X^(j)∥

_q^q),

where X(⁽ⁱ⁾ and X^(j) denote i-th and j-th vectors, respectively, and

7. The method according to claim 5, wherein the similarity calculated using the exponential attenuation function is calculated by using the following expression,

8. The method according to claim 5, wherein the similarity calculated using the exponential attenuation function is calculated by using the following expression,

18. A non-transitory computer program product tangibly embodying non-transitory computer readable instruction which when implemented cause a computer to carry out the steps of the method according to claim 5.

20. A computer estimate of location label of a vector dataset that has no location label from a plurality of vector datasets that have location labels, wherein said estimate is obtained by a method according to claim 5.

9. A computer-implemented location estimation method for estimating a location from radio signal strength datasets, the method comprising the steps of:

preparing a plurality of radio signal strength vector datasets with location labels and a plurality of radio signal strength vector datasets without location labels, respectively, and then storing the prepared datasets in the computer device;

setting an initial value of the plausibility score f⁽ⁱ⁾(c) wherein i=1 . . . N and

wherein N denotes the number of all the prepared radio signal strength vector datasets such that each of the radio signal strength vector datasets with location labels and the radio signal strength vector datasets without location labels has a location label c;

calculating the similarity between the vector dataset without any location label and each neighboring vector dataset with a location label using a q-norm and an exponential attenuation function, wherein 0<

q<

1; and

iteratively executing the step of calculating f⁽ⁱ⁾(c),

wherein at least one step of the method is carried out on the computer device.

10. The method according to claim 9, wherein the calculating step includes the following steps:

calculating similarity W^(i,j) for each combination of i and j wherein i,j=1 . . . N, by using any one of a q-norm wherein 0<

q<

1, of the radio signal strength vector and an exponential attenuation function; and

calculating f⁽ⁱ⁾(c) for each of the radio signal strength vector datasets without location labels, by using the following expression

11. The method according to claim 10, wherein the step of calculating the similarity W^(i,j) includes the following steps of:

calculating the temporal similarity W_t^(i,j); and

choosing, as the similarity W^(i,j), one having the larger value from the temporal similarity W_t^(i,j) and the spatial similarity calculated by using any one of the q-norm and the exponential attenuation function.

12. The method according to claim 10, wherein the spatial similarities are calculated using the following expression using the q-norm,

W_X^(i,j)=exp(−

∥

X⁽ⁱ⁾−

X^(j)∥

_q^q),

where X⁽ⁱ⁾ denotes the i-th radio signal strength vector, and

13. The method according to claim 12, wherein both q and σ

are set at 0.5.

14. The method according to claim 10, wherein the spatial similarities are calculated by using the following expression with an exponential attenuation function,

15. The method according to claim 10, wherein the spatial similarities are calculated by using the following expression using exponential attenuation function,

16. The method according to claim 11, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

W_t^(i,j)=p·

δ

(TID⁽ⁱ⁾=TID^(j))·

δ

(|t⁽ⁱ⁾−

t^(j)|=1)

where 0<

p≦

1 is a constant parameter, TID⁽ⁱ⁾ is the trace ID to which the i-th vector belongs, and t⁽ⁱ⁾ is the time of observation of the i-th vector.

17. The method according to claim 11, wherein the temporal similarity W_t^(i,j) is calculated by using the following expression,

W_t^(i,j)=p·

δ

(TID⁽ⁱ⁾=TID^(j))·

exp(−

∥

t⁽ⁱ⁾−

t^(j)∥

_r^r)

where

19. A non-transitory computer program product tangibly embodying computer readable instruction which when implemented cause a computer to carry out the steps of the method according to claim 9.