Modeling location histories

• US 20060085177A1
• Filed: 10/19/2004
• Published: 04/20/2006
• 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
• Granted Patent: US 7,720,652 B2
• Time in Patent Office: Days
• US Class Current: 703/22
• 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. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct a device to convert a location history to a stochastic model of the location history.

2. The one or more processor-accessible media as recited in claim 1, wherein the conversion involves application of at least one recurring time period.

3. The one or more processor-accessible media as recited in claim 2, wherein the at least one recurring time period comprises a cycle that is divided into a plurality of intervals, the cycle periodically repeating.

4. The one or more processor-accessible media as recited in claim 1, wherein the stochastic model comprises a two-dimensional matrix having multiple intervals, each interval of the multiple intervals including a plurality of entries;

each entry of a particular plurality of entries for a particular interval including a probability that an object is present at a corresponding location during the particular interval.

5. The one or more processor-accessible media as recited in claim 1, wherein the processor-executable instructions, when executed, direct the device to perform the conversion by training the stochastic model using data from the location history.

6. The one or more processor-accessible media as recited in claim 5, wherein the data from the location history comprises at least one of stays or destinations.

7. The one or more processor-accessible media as recited in claim 6, wherein the destinations comprise destinations clustered from stays.

8. The one or more processor-accessible media as recited in claim 5, wherein the processor-executable instructions, when executed, direct the device to effectuate the training by traversing each respective interval of multiple cycles of data from the location history and adding each respective corresponding location to a training matrix.

9. The one or more processor-accessible media as recited in claim 8, wherein the processor-executable instructions, when executed, direct the device to further effectuate the training by normalizing each interval with regard to a total number of cycles of the multiple cycles to determine relative probabilities per corresponding location for each interval.

10. The one or more processor-accessible media as recited in claim 5, wherein the processor-executable instructions, when executed, direct the device to effectuate the training without using transitional probabilities.

11. The one or more processor-accessible media as recited in claim 5, wherein the processor-executable 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.

12. The one or more processor-accessible media as recited in 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.

13. The one or more processor-accessible media as recited in claim 1, wherein the processor-executable instructions, when executed, direct the device to perform an evaluation of a subject location history using the stochastic model.

14. The one or more processor-accessible media as recited in claim 13, wherein the processor-executable 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.

15. The one or more processor-accessible media as recited in claim 14, wherein the processor-executable 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.

16. The one or more processor-accessible media as recited in claim 1, wherein the processor-executable instructions, when executed, direct the device to perform an object location prediction using the stochastic model.

17. The one or more processor-accessible media as recited in claim 1, wherein the processor-executable instructions, when executed, direct the device to construct a fake location history using the stochastic model.

18. The one or more processor-accessible media as recited in claim 17, wherein the processor-executable 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.

19. The one or more processor-accessible media as recited in claim 1, wherein the one or more processor-accessible media comprise at least one of (i) one or more storage media or (ii) one or more transmission media.

20. An arrangement for modeling location histories, the arrangement comprising:

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 a recurring time period.

21. The arrangement as recited in claim 20, further comprising:

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

22. The arrangement as recited in claim 20, further comprising:

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

23. The arrangement as recited in claim 20, wherein the training means comprises:

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

24. The arrangement as recited in claim 23, wherein the addition means comprises:

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

25. The arrangement as recited in claim 20, wherein the training means comprises:

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

26. The arrangement as recited in claim 20, wherein the arrangement comprises at least one of (i) one or more processor-accessible media or (ii) at least one device.

27. The arrangement as recited in claim 20, 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.

28. A method comprising:

adding object locations to a training matrix for intervals of a designated cycle from a location history;

normalizing the intervals with regard to a number of cycles addressed in the adding to determine relative probabilities per location for each interval; and

building a stochastic model by recording respective location probabilities determined in the normalizing for corresponding intervals in a location history model matrix.

29. The method as recited in claim 28, further comprising:

effectuating and/or implementing an application using the location history model matrix, the application selected from a group comprising;

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

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

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

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

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

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

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

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

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

33. One or more processor-accessible media comprising processor-executable instructions that include a location history model data structure, the location history model data structure comprising a two-dimensional matrix having a plurality of probabilities;

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

each probability of the plurality of probabilities associated with an object location of the multiple object locations and corresponding to an interval of the multiple intervals.

34. The one or more processor-accessible media as recited in claim 33, wherein the processor-executable instructions, when executed, direct a device to train the location history model data structure from a location history.

35. The one or more processor-accessible media as recited in claim 33, wherein the processor-executable instructions, when executed, direct a device to perform an evaluation of a subject location history using the location history model data structure;

the location history model data structure used to ascertain a probability associated with each object location for any given interval of the subject location history.

36. A device comprising:

at least one processor; and

one or more media including processor-executable instructions that are capable of being executed by the at least one processor, the processor-executable instructions including;

a location history model data structure, the location history model data structure 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.

37. The device as recited in claim 36, 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 location history model data structure.

38. The device as recited in claim 36, 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.

39. The device as recited in claim 36, 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.