Parsing location histories

• US 20060101377A1
• Filed: 10/19/2004
• Published: 05/11/2006
• Est. Priority Date: 10/19/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Uyttendaele, Matthew T., Oliver, Nuria M., Toyama, Kentaro, Douceur, John R., Ringger, Eric K., Robbins, Daniel C., Hariharan, Ramaswamy, Cutler, Ross G.
• Granted Patent: US 7,868,786 B2
• Time in Patent Office: Days
• US Class Current: 717/104
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A location history is a collection of locations over time for an object. A stay is a single instance of an object spending some time in one place, and a destination is any place where one or more objects have experienced a stay. Location histories are parsed using stays and destinations. In a described implementation, each location of a location history is recorded as a spatial position and a corresponding time at which the spatial position is acquired. Stays are extracted from a location history by analyzing locations thereof with regard to a temporal threshold and a spatial threshold. Specifically, two or more locations are considered a stay if they exceed a minimum stay duration and are within a maximum roaming distance. Each stay includes a location, a starting time, and an ending time. Destinations are produced from the extracted stays using a clustering operation and a predetermined scaling factor.

Claims

1. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct a device to perform actions comprising:

ascertaining a next location that exceeds a minimum stay duration with respect to a current location;

determining if the next location is within a maximum roaming distance with respect to the current location;

if the next location is determined to be within the maximum roaming distance, extracting a stay that is associated with the current location and the next location.

2. The one or more processor-accessible media as recited in claim 1, wherein the action of ascertaining comprises actions of:

determining a difference between a timestamp corresponding to the current location and a timestamp corresponding to the next location; and

determining if the difference is greater than the minimum stay duration.

3. The one or more processor-accessible media as recited in claim 1, wherein the action of determining comprises actions of:

calculating a distance between the current location and the next location; and

determining if the distance is less than the maximum roaming distance.

4. The one or more processor-accessible media as recited in claim 1, wherein the action of extracting comprises an action of:

extracting the stay such that the stay is assigned (i) a location responsive to a center calculated from a set of locations that includes the current location and the next location and (ii) a start time responsive to a timestamp corresponding to the current location.

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 a further action comprising:

ascertaining a location that is temporally most distant from the current location but within the maximum roaming distance.

6. The one or more processor-accessible media as recited in claim 5, wherein the processor-executable instructions, when executed, direct the device to perform a further action comprising:

calculating a center of a location set that is bounded by the current location and the most distant location.

7. The one or more processor-accessible media as recited in claim 6, wherein the action of calculating comprises an action of:

calculating a geometric center of the location set;

or

calculating a medoid center of the location set.

8. The one or more processor-accessible media as recited in claim 6, wherein the action of extracting comprises an action of:

extracting the stay such that the stay is assigned (i) a location responsive to the calculated center, (ii) a start time responsive to a timestamp corresponding to the current location, and (iii) an end time responsive to a timestamp corresponding to the most distant location.

9. The one or more processor-accessible media as recited in claim 1, wherein the processor-executable instructions, when executed, direct the device to perform further actions comprising:

accepting raw location data having multiple locations as input, the multiple locations including the current location and the next location; and

selecting the current location from the raw location data.

10. The one or more processor-accessible media as recited in claim 9, wherein each location of the multiple locations of the raw location data includes a spatial location and a timestamp.

11. The one or more processor-accessible media as recited in claim 9, wherein the processor-executable instructions, when executed, direct the device to perform further actions comprising:

extracting multiple stays from the multiple locations of the raw location data; and

clustering the extracted multiple stays into multiple destinations in accordance with a selected scale.

12. The one or more processor-accessible media as recited in claim 11, wherein the processor-executable instructions, when executed, direct the device to perform a further action comprising:

effectuating and/or implementing an application using the multiple stays and/or the multiple destinations, the application selected from a group comprising;

time-based patterns of behavior, location modeling and fusion, multi-object location interactions, destination statistics, and scale-dependent pattern analysis.

13. 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.

14. A device that is capable of accessing raw location data having multiple locations as input, each location of the multiple locations including a spatial location and a timestamp;

the device adapted to extract multiple stays from the multiple locations based on a temporal minimum and responsive to a spatial maximum.

15. The device as recited in claim 14, wherein each stay of the extracted multiple stays is defined by a spatial location, a start time, and an end time.

16. The device as recited in claim 14, wherein two locations of the multiple locations at least partially form a stay of the extracted multiple stays when the two locations comport with the temporal minimum and the spatial maximum.

17. The device as recited in claim 14, wherein the multiple locations include a first location and a second location;

the first location having a first spatial location and a first timestamp, and the second location having a second spatial location and a second timestamp; and

wherein the first and second locations at least partially form a stay if a difference between the first timestamp and the second timestamp exceeds the temporal minimum and if a distance between the first spatial location and the second spatial location is within the spatial maximum.

18. The device as recited in claim 14, wherein at least one stay of the extracted multiple stays is formed from three or more locations of the multiple locations, the three or more locations forming the at least one stay comporting with the temporal minimum and the spatial maximum.

19. The device as recited in claim 18, wherein the device is further adapted to calculate a center of a location set including the three or more locations;

and wherein the device is further adapted to assign a location to the at least one stay that is equivalent to the calculated center of the location set.

20. The device as recited in claim 14, wherein the locations of the multiple locations are analyzed in increasing chronological order and/or in decreasing chronological order.

21. The device as recited in claim 14, wherein the device is further adapted to apply to the extracted multiple stays a clustering operation in conjunction with a selected scale to produce multiple destinations.

22. The device as recited in claim 21, wherein the device is further adapted to effectuate and/or implement an application using the extracted multiple stays and/or the produced multiple destinations, the application selected from a group comprising:

time-based patterns of behavior, location modeling and fusion, multi-object location interactions, destination statistics, and scale-dependent pattern analysis.

23. An arrangement for parsing location histories, the arrangement comprising:

temporal means for ascertaining candidate locations of a location history with a time window;

spatial means for instituting a roaming range for the candidate locations ascertained by the temporal means; and

extraction means for extracting stays from the location history using the temporal means and the spatial means.

24. The arrangement as recited in claim 23, wherein the temporal means ascertains a candidate location by applying the time window at a current location of the location history and ascertaining a next location that is outside the time window.

25. The arrangement as recited in claim 23, wherein the spatial means institutes the roaming range by determining if a candidate location is within the roaming range with respect to a current location of the location history.

26. The arrangement as recited in claim 23, wherein the extraction means extracts a stay from the location history when a distance between a spatial location of a candidate location that is ascertained by the temporal means and a spatial location of a current location being analyzed is less than the roaming range instituted by the spatial means.

27. The arrangement as recited in claim 23, further comprising:

ascertainment means for ascertaining a location of the location history that is temporally most distant from a current location being analyzed but still within the roaming range instituted by the spatial means.

28. The arrangement as recited in claim 27, further comprising:

calculation means for calculating a center of a location set that is bounded by (i) the current location being analyzed and (ii) the most distant location as ascertained by the ascertainment means.

29. The arrangement as recited in claim 28, wherein the extraction means comprises:

location assignment means for assigning to an extracted stay a location responsive to the center of the location set as calculated by the calculation means;

start time assignment means for assigning to the extracted stay a start time responsive to a timestamp corresponding to the current location being analyzed; and

end time assignment means for assigning to the extracted stay an end time responsive to a timestamp corresponding to the most distant location as ascertained by the ascertainment means.

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

31. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct a device to perform actions comprising:

accepting raw location data as input, the raw location data including a plurality of location data points, each location data point of the plurality of location data points including a location and a corresponding timestamp; and

producing a plurality of destinations from the raw location data using a plurality of stays extracted from the raw location data, the plurality of stays associated with a temporal aspect of the raw location data.

32. The one or more processor-accessible media as recited in claim 31, wherein the action of producing comprises an action of:

applying a clustering operation to the plurality of stays in accordance with a scaling factor.

33. The one or more processor-accessible media as recited in claim 32, wherein each stay of the plurality of stays comprises a location, a starting time, and an ending time;

and wherein each destination of the plurality of destinations comprises a location, and the plurality of destinations are associated with the scaling factor.

34. The one or more processor-accessible media as recited in claim 31, wherein the processor-executable instructions, when executed, direct the device to perform a further action comprising:

extracting the plurality of stays from the raw location data by enforcing a minimum stay duration for two or more location data points of the plurality of location data points to qualify as a stay.

35. The one or more processor-accessible media as recited in claim 31, wherein the processor-executable instructions, when executed, direct the device to perform a further action comprising:

effectuating and/or implementing an application using the plurality of stays and/or the plurality of destinations, the application selected from a group comprising;

time-based patterns of behavior, location modeling and fusion, multi-object location interactions, destination statistics, and scale-dependent pattern analysis.

36. One or more processor-accessible media comprising processor-executable instructions that, when executed, direct a device to perform actions comprising:

accessing a plurality of stays, each stay of the plurality of stays comprising a location and a corresponding time period; and

clustering the plurality of stays to produce a plurality of destinations.

37. The one or more processor-accessible media as recited in claim 36, wherein the action of clustering comprises actions of:

merging locations of the plurality of stays into a plurality of clusters in accordance with a scale setting; and

creating respective destinations of the plurality of destinations from the plurality of clusters responsive to respective calculated centers of respective clusters of the plurality of clusters.

38. The one or more processor-accessible media as recited in claim 36, wherein the processor-executable instructions, when executed, direct the device to perform a further action comprising:

extracting the plurality of stays from a location history using a temporal threshold and a spatial threshold.

39. The one or more processor-accessible media as recited in claim 36, wherein the processor-executable instructions, when executed, direct the device to perform a further action comprising:

effectuating and/or implementing an application using the plurality of stays and/or the plurality of destinations, the application selected from a group comprising;

time-based patterns of behavior, location modeling and fusion, multi-object location interactions, destination statistics, and scale-dependent pattern analysis.