Modeling location histories

• US 7,720,652 B2
• Filed: 10/19/2004
• Issued: 05/18/2010
• Est. Priority Date: 10/19/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toyama, Kentaro, Hariharan, Ramaswamy
• Primary Examiner(s): Shah; Kamini S
• Assistant Examiner(s): Alhija; Saif A
• Application Number:
  US10/968,862
• Publication Number:
  US 20060085177A1
• Time in Patent Office: 2,037 Days
• Field of Search: 703/2, 703/22
• US Class Current: 703/2
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network

Abstract

A location history is a collection of locations over time for an object. By applying a recurring time period to a location history, it can be converted into a stochastic model of the location history. For example, a location history can be reorganized based on intervals that subside a recurring cycle. In a described implementation, training a location history model involves traversing each interval of multiple cycles of a target location history. After each object location at each interval is entered into a training matrix, the intervals can be normalized to determine relative probabilities per location for each interval of a designated cycle. The training and resulting location history model can be Markovian or non-Markovian. Applications include probabilistic location estimation, fusion of location estimates, location-history simulation, optimal scheduling, transition analysis, clique analysis, and so forth.

Claims

1. An article of manufacture comprising:

a storage medium; and

a plurality of executable instructions stored on the storage medium that, when executed, direct a device to convert a location history to a stochastic model of the location history by applying at least one recurring time period to the location history, the recurring time period being divided into a number of time intervals, the stochastic model comprising a multi-dimensional matrix that includes multiple entries each corresponding to a combination of one of the time intervals and one of multiple locations, each entry including at least one probability that an object is present at the corresponding one of the locations during the one of the time intervals, the probability being calculated by dividing a total number of times that the location history shows the object as being at the corresponding one of the multiple locations during the corresponding one of the time intervals by a total number of recurrences of the time period.

2. The article of claim 1, wherein the at least one recurring time period comprises a cycle, the cycle periodically repeating.

3. The article of claim 1, wherein the multi-dimensional matrix is a two-dimensional matrix.

4. The article of claim 1, wherein the instructions, when executed, direct the device to perform the conversion by training the stochastic model using data from the location history.

5. The article of claim 4, wherein the data from the location history comprises at least one of stays or destinations.

6. The article of claim 4, wherein the data from the location history comprises destinations clustered from stays.

7. The article of claim 4, wherein the instructions, when executed, direct the device to effectuate the training by traversing each respective time interval of multiple recurring time periods of data from the location history and adding each respective corresponding location to a training matrix.

8. The article of claim 7, wherein the instructions, when executed, direct the device to further effectuate the training by normalizing each interval with regard to the total number of recurring time periods of the multiple recurring time periods to determine relative probabilities per corresponding location for each interval.

9. The article of claim 4, wherein the instructions, when executed, direct the device to effectuate the training without using transitional probabilities.

10. The article of claim 4, wherein the instructions, when executed, direct the device to effectuate the training by accounting for a location of a previous interval when determining a probability of a location of a current interval.

11. The article of claim 1, wherein the stochastic model comprises a three-dimensional matrix;

the three dimensions of the three-dimensional matrix comprising intervals, locations for a previous interval, and locations for a current interval.

12. The article of claim 1, wherein the instructions, when executed, direct the device to perform an evaluation of a subject location history using the stochastic model.

13. The article of claim 12, wherein the instructions, when executed, direct the device to effectuate the evaluation by ascertaining a respective probability for each respective interval of a cycle based on a corresponding location of an object extracted from the subject location history.

14. The article of claim 13, wherein the instructions, when executed, direct the device to further effectuate the evaluation by performing a combination operation on the ascertained respective probabilities for each respective interval of the cycle from the subject location history.

15. The article of claim 1, wherein the instructions, when executed, direct the device to perform an object location prediction using the stochastic model.

16. The article of claim 1, wherein the instructions, when executed, direct the device to construct a fake location history using the stochastic model.

17. The article of claim 16, wherein the instructions, when executed, direct the device to effectuate the construction of the fake location history by creating cumulative distributive functions (CDFs) utilizing the stochastic model and by running Monte Carlo style simulations using the CDFs.

18. A system for modeling location histories, the system comprising:

a processor;

memory coupled to the processor;

architecture means for architecting a stochastic model of a location history; and

training means for training the stochastic model from the location history by applying at least one recurring time period to the location history, the recurring time period being divided into a number of time intervals, the stochastic model comprising a multi-dimensional matrix that includes multiple entries each corresponding to a combination of one of the time intervals and one of multiple locations, each entry including at least one probability that an object is present at the corresponding one of the location during the one of the time intervals, the probability being calculated by dividing a total number of times that the location history shows the object as being at the corresponding one of the multiple locations during the corresponding one of the time intervals by a total number of recurrences of the time period.

19. The system as recited in claim 18, further comprising:

evaluation means for evaluating a subject location history with regard to the stochastic model of the location history.

20. The system as recited in claim 18, further comprising:

prediction means for predicting a location of an object during at least one time interval of a time period utilizing the stochastic model of the location history, the location history being for the object.

21. The system as recited in claim 18, wherein the training means comprises:

addition means for adding a location of an object corresponding to an time interval of a designated time period in a training matrix for multiple time intervals of multiple time periods of the location history.

22. The system as recited in claim 21, wherein the addition means comprises:

transitional addition means for adding a current location of the object corresponding to a current time interval in the training matrix in dependence on a previous location of the object corresponding to a previous time interval.

23. The system as recited in claim 18, wherein the training means comprises:

normalization means for normalizing multiple time intervals of a matrix, with regard to a number of time periods of the location history used by the training means, to determine relative probabilities per location for each time interval of the multiple time intervals.

24. The system as recited in claim 18, further comprising:

effectuation means for implementing an application using the stochastic model of the location history, the application selected from a group comprising;

probabilistic location estimation, fusion of location estimates, location-history simulation, optimal scheduling, transition analysis, and clique analysis.

25. A method comprising:

adding, by a computing device, object locations to a training matrix for time intervals of a designated cycle from a location history;

normalizing, by the computing device, the time intervals with regard to a number of the cycles addressed in the adding to determine relative probabilities an object is present per location for each interval, each probability being calculated by dividing a total number of times that the location history shows the object as being at one of the locations during one of the time intervals by a total number of recurrences of the cycle;

building and storing, by the computing device, a stochastic model by recording the respective location probabilities determined in the normalizing for corresponding intervals in a location history model matrix; and

implementing, by the computing device, an application using a stored location history model matrix, the application selected from a group comprising;

a probabilistic location estimation, a fusion of location estimates, a location-history simulation, an optimal scheduling, a transition analysis, and a clique analysis.

26. The method as recited in claim 25, wherein the adding comprises:

inspecting a particular time interval of a particular cycle of the location history;

determining a particular object location during the particular time interval from the location history; and

incrementing in the training matrix a subtotal for a matrix interval corresponding to the particular time interval at an object location corresponding to the particular object location.

27. The method as recited in claim 25, wherein the adding comprises:

adding the object locations to the training matrix for time intervals of the designated cycle from the location history while accounting for previous object locations in previous time intervals.

28. The method as recited in claim 25, wherein the adding comprises:

adding to the object locations using split ratios to account for intra-interval location transitions.

29. A device comprising:

at least one processor; and

one or more computer program products embodied on computer readable storage media including processor-executable instructions, the processor-executable instructions including;

a stochastic location history model comprising a three-dimensional matrix having a plurality of probabilities;

a first dimension comprising multiple intervals of a cycle, a second dimension comprising multiple previous object locations, and a third dimension comprising multiple current object locations;

each probability of the plurality of probabilities corresponding to an intersection of the second and third dimensions, each particular probability associated with a particular current object location given an intersecting previous object location, each probability comprising a probability that an object is present at the associated current object location during a corresponding interval given the intersecting previous object location, the probability being calculated by dividing a total number of times that the location history shows the object as being at the corresponding one of the multiple locations during the corresponding one of the time intervals by a total number of recurrences of the time period, wherein the processor-executable instructions, when executed, direct the device to predict an object'"'"'s location during a particular interval using at least one cumulative distributive function (CDF) that is derived from the stochastic location history model.

30. The device as recited in claim 29, wherein a two-dimensional matrix, which is formed from the second and third dimensions of the three-dimensional matrix, exists for each interval of the multiple intervals of the cycle of the first dimension of the three-dimensional matrix.

31. The device as recited in claim 29, wherein the processor-executable instructions, when executed, direct the device to effectuate and/or implement an application using the location history model data structure, the application selected from a group comprising:

probabilistic location estimation, fusion of location estimates, location-history simulation, optimal scheduling, transition analysis, and clique analysis.