Modeling significant locations

• US 9,267,805 B2
• Filed: 09/06/2013
• Issued: 02/23/2016
• Est. Priority Date: 06/07/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Marti, Lukas M., Dal Santo, Michael P., Huang, Ronald Keryuan
• Primary Examiner(s): Huynh, Luke
• Application Number:
  US14/020,689
• Publication Number:
  US 20140364149A1
• Time in Patent Office: 900 Days
• Field of Search: 701/521, 455/456.3, 235411-413
• US Class Current: 1/1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: G01S 5/0294 Trajectory determination or predictive filtering, e.g. target tracking or Kalman filtering
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 88/005 Data network PoA devices

Abstract

Techniques for modeling significant locations are described. A significant location can be a location that is significant to a user of a mobile device for a variety of reasons. The mobile device can determine that a place or region is a significant location upon determining that, with sufficient certainty, the mobile device has stayed at the place or region for a sufficient amount of time. The mobile device can construct a state model that is an abstraction of one or more significant locations. The state model can include states representing the significant locations, and transitions representing movement of the mobile device between the locations. The mobile device can use the state model to provide predictive user assistance.

Claims

1. A method comprising:

receiving, by a mobile device and from a location determination subsystem of the mobile device, a plurality of locations of the mobile device, each location being associated with a timestamp indicating a time the location was determined by the location determination subsystem, the plurality of locations being ordered sequentially based on timestamps of the locations;

determining, by the mobile device and based on a clustering condition, that two or more consecutive locations in the ordered plurality of locations form a location cluster, the location cluster indicating that the mobile device has stayed at a geographic location that is sufficiently significant to be represented in a state model for forecasting a movement of the mobile device;

determining, by the mobile device and based on the location cluster, the state model, including designating the significant location as a state in the state model and representing each movement of the mobile device from a first significant location to a second significant location as a transition from a first state representing the first significant location to a second state representing the second significant location, the transition being associated with a transition start time and a transition end time; and

providing the state model to a forecasting subsystem of the mobile device for generating a forecast that a future location of the mobile device at a given future time is one of the significant locations represented in the state model, wherein generating the forecast is based on a current time, the future time, a current location, and a probability density determined based on the states and transitions of the state model.

2. The method of claim 1, wherein receiving the locations comprises reading the location from the location determination subsystem one at a time, each reading of the location determination subsystem being triggered by an activation of the location determination subsystem by an application program or function external to a location forecasting application program or function.

3. The method of claim 1, wherein the clustering condition specifies that:

the consecutive locations are identical, or a distance between each pair of the consecutive locations is less than a spatial proximity threshold; and

a time difference between a timestamp associated with a first location among the consecutive locations and a timestamp associated with a last location among the consecutive locations is greater than a temporal proximity threshold, wherein the significant location is a location where the mobile device has stayed for a time period at least as long as indicated by the temporal proximity threshold.

4. The method of claim 1, wherein determining the location cluster comprises:

validating each of the two or more consecutive locations based on an uncertainty value associated with each respective location, the uncertainty value indicating a likelihood that the respective location is determined correctly by the location determination subsystem;

excluding one or more outliers from the consecutive locations, each outlier being a location associated with an uncertainty value that exceeds a threshold; and

determining the location cluster using the validated locations that are not outliers.

5. The method of claim 1, wherein the significant location is determined based on the location cluster by applying a recursive filter having a constant gain to locations in the location cluster.

6. The method of claim 1, wherein each state in the state model is associated with state entry timestamp and a state exit timestamp.

7. The method of claim 1, wherein determining the state model comprises one of:

upon determining that the location cluster is already designated as the state in the state model, adding a transition of the mobile device between the state and another state to the state model or adding a state entry time and a state exit timestamp to the state;

or

upon determining that the location cluster is not already represented as the state in the state model, adding the location cluster to the state model.

8. The method of claim 1, comprising:

determining that at least one attribute of the state model satisfies a statistical threshold;

and then determining a semantic meaning of the state and a semantic meaning of the transition.

9. The method of claim 8, wherein:

the statistical threshold comprises a longevity of each state;

determining the semantic meaning of the state comprises determining whether the state relates to an activity pattern of life; and

determining the semantic meaning of the transition is based an attribute of a commute between two activities of life.

10. The method of claim 1, comprising adjusting states in the state model over time using an autoregressive filter, wherein adjusting the states includes removing a stale state from the state model upon determining that the mobile device has not visited a significant location represented by the state model for a given period of time.

11. A system comprising:

one or more processors; and

a non-transitory computer-readable medium coupled to the one or more processors and storing instructions operable to cause the one or more processors to perform operations comprising;

receiving a plurality of locations of a mobile device, each location being associated with a timestamp indicating a time the location was determined by the location determination subsystem, the plurality of locations being ordered sequentially based on timestamps of the locations;

determining, based on a clustering condition, that two or more consecutive locations in the ordered plurality of locations form a location cluster, the location cluster indicating that the mobile device has stayed at a geographic location that is sufficiently significant to be represented in a state model for forecasting a movement of the mobile device;

determining, based on the location cluster, the state model, including designating the significant location as a state in the state model and representing each movement of the mobile device from a first significant location to a second significant location as a transition from a first state representing the first significant location to a second state representing the second significant location, the transition being associated with a transition start time and a transition end time; and

providing the state model to a forecasting subsystem of the mobile device for generating a forecast that a future location of the mobile device at a given future time is one of the significant locations represented in the state model.

12. The system of claim 11, wherein receiving the locations comprises reading the location from the location determination subsystem one at a time, each reading of the location determination subsystem being triggered by an activation of the location determination subsystem by an application program or function external to a location forecasting application program or function.

13. The system of claim 11, wherein the clustering condition specifies that:

the consecutive locations are identical, or a distance between each pair of the consecutive locations is less than a spatial proximity threshold; and

a time difference between a timestamp associated with a first location among the consecutive locations and a timestamp associated with a last location among the consecutive locations is greater than a temporal proximity threshold, wherein the significant location is a location where the mobile device has stayed for a time period at least as long as indicated by the temporal proximity threshold.

14. The system of claim 11, wherein determining the location cluster comprises:

validating each of the two or more consecutive locations based on an uncertainty value associated with each respective location, the uncertainty value indicating a likelihood that the respective location is determined correctly by the location determination subsystem;

excluding one or more outliers from the consecutive locations, each outlier being a location associated with an uncertainty value that exceeds a threshold; and

determining the location cluster using the validated locations that are not outliers.

15. The system of claim 11, wherein the significant location is determined based on the location cluster by applying a recursive filter having a constant gain to locations in the location cluster.

16. The system of claim 11, wherein each state in the state model is associated with state entry timestamp and a state exit timestamp.

17. The system of claim 11, wherein determining the state model comprises one of:

upon determining that the location cluster is already designated as the state in the state model, adding a transition of the mobile device between the state and another state to the state model or adding a state entry time and a state exit timestamp to the state;

or

upon determining that the location cluster is not already represented as the state in the state model, adding the location cluster to the state model.

18. The system of claim 11, the operations comprising:

determining that at least one attribute of the state model satisfies a statistical threshold; and

then

determining a semantic meaning of the state and a semantic meaning of the transition.

19. The system of claim 18, wherein:

the statistical threshold comprises a longevity of each state;

determining the semantic meaning of the state comprises determining whether the state relates to an activity pattern of life; and

determining the semantic meaning of the transition is based an attribute of a commute between two activities of life.

20. The system of claim 11, the operations comprising adjusting states in the state model over time using an autoregressive filter, wherein adjusting the states includes removing a stale state from the state model upon determining that the mobile device has not visited a significant location represented by the state model for a given period of time.

21. A non-transitory computer-readable medium coupled to one or more processors and storing instructions operable to cause the one or more processors to perform operations comprising:

receiving a plurality of locations of the mobile device, each location being associated with a timestamp indicating a time the location was determined by the location determination subsystem, the plurality of locations being ordered sequentially based on timestamps of the locations;

determining, based on a clustering condition, that two or more consecutive locations in the ordered plurality of locations form a location cluster, the location cluster indicating that the mobile device has stayed at a geographic location that is sufficiently significant to be represented in a state model for forecasting a movement of the mobile device;

determining, based on the location cluster, the state model, including designating the significant location as a state in the state model and representing each movement of the mobile device from a first significant location to a second significant location as a transition from a first state representing the first significant location to a second state representing the second significant location, the transition being associated with a transition start time and a transition end time; and

providing the state model to a forecasting subsystem of the mobile device for generating a forecast that a future location of the mobile device at a given future time is one of the significant locations represented in the state model.

22. The non-transitory computer-readable medium of claim 21, wherein receiving the locations comprises reading the location from the location determination subsystem one at a time, each reading of the location determination subsystem being triggered by an activation of the location determination subsystem by an application program or function external to a location forecasting application program or function.

23. The non-transitory computer-readable medium of claim 21, wherein the clustering condition specifies that:

the consecutive locations are identical, or a distance between each pair of the consecutive locations is less than a spatial proximity threshold; and

a time difference between a timestamp associated with a first location among the consecutive locations and a timestamp associated with a last location among the consecutive locations is greater than a temporal proximity threshold, wherein the significant location is a location where the mobile device has stayed for a time period at least as long as indicated by the temporal proximity threshold.

24. The non-transitory computer-readable medium of claim 21, wherein determining the location cluster comprises:

validating each of the two or more consecutive locations based on an uncertainty value associated with each respective location, the uncertainty value indicating a likelihood that the respective location is determined correctly by the location determination subsystem;

excluding one or more outliers from the consecutive locations, each outlier being a location associated with an uncertainty value that exceeds a threshold; and

determining the location cluster using the validated locations that are not outliers.

25. The non-transitory computer-readable medium of claim 21, wherein the significant location is determined based on the location cluster by applying a recursive filter having a constant gain to locations in the location cluster.

26. The non-transitory computer-readable medium of claim 21, wherein each state in the state model is associated with state entry timestamp and a state exit timestamp.

27. The non-transitory computer-readable medium of claim 21, wherein determining the state model comprises one of:

upon determining that the location cluster is already designated as the state in the state model, adding a transition of the mobile device between the state and another state to the state model or adding a state entry time and a state exit timestamp to the state;

or

upon determining that the location cluster is not already represented as the state in the state model, adding the location cluster to the state model.

28. The non-transitory computer-readable medium of claim 21, the operations comprising:

determining that at least one attribute of the state model satisfies a statistical threshold; and

then

determining a semantic meaning of the state and a semantic meaning of the transition.

29. The non-transitory computer-readable medium of claim 28, wherein:

the statistical threshold comprises a longevity of each state;

determining the semantic meaning of the state comprises determining whether the state relates to an activity pattern of life; and

determining the semantic meaning of the transition is based an attribute of a commute between two activities of life.

30. The non-transitory computer-readable medium of claim 21, the operations comprising adjusting states in the state model over time using an autoregressive filter, wherein adjusting the states includes removing a stale state from the state model upon determining that the mobile device has not visited a significant location represented by the state model for a given period of time.