IDENTIFYING INTERESTING LOCATIONS

• US 20100211308A1
• Filed: 02/19/2009
• Published: 08/19/2010
• Est. Priority Date: 02/19/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Xie, Xing, Zheng, Yu, Zhang, Lizhu
• Application Number:
  US12/388,901
• Publication Number:
  US 20100211308A1
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence

Abstract

Interesting location identification embodiments are presented that generally involve identifying and providing the interesting locations found in a given geospatial region. This is accomplished by modeling the location histories of multiple individuals who traveled through the region of interest, and identifying interesting locations in the region based on the number of individuals visiting a location weighted in terms of the travel experience of those individuals. A prescribed number of the top most interesting locations in a specified region can be provided upon request. In addition, prescribed numbers of the top most popular travel sequences through the interesting locations and the top most experienced travelers in the specified region can be provided as well.

Claims

1. A computer-implemented process for identifying interesting locations in a geospatial region, comprising:

using a computer to perform the following process actions,

modeling location histories of multiple individuals who traveled through the region, and

identifying interesting locations in the region based on a number of individuals visiting a location in the region weighted in terms of the travel experience of the individuals visiting the location.

2. The process of claim 1, wherein the process action of modeling the location histories of multiple individuals who traveled through the region, comprises the actions of:

inputting location histories of said multiple individuals, wherein the location history for an individual comprises a log of the geospatial locations of the individual captured periodically over a period of time;

identifying stay points from the location histories, wherein a stay point is a geospatial location in said region which is within a prescribed maximum distance of locations where an individual spent a period of time exceeding a prescribed minimum period; and

generating a tree-based hierarchical graph (TBHG) from the identified stay points, wherein the TBHG models the multiple individuals'"'"' stay points as interesting locations on each of a plurality of scaled geospatial levels.

3. The process of claim 2, wherein the process action of inputting location histories comprises an action of inputting a global positioning system (GPS) data logs each comprising a collection of GPS points representing the geospatial locations of an individual captured periodically over a period of time, wherein each GPS point comprises a latitude, a longitude and a timestamp.

4. The process of claim 3, wherein the process action of identifying stay points, comprises the actions of:

parsing the GPS logs for each individual into GPS trajectories, wherein each GPS trajectory comprises a series of trajectory segments formed by splitting a curve connecting sequential GPS points based on their timestamps wherein each segment corresponds to a part of the curve having a time interval between beginning and ending GPS trajectory points that exceeds a prescribed time period;

for each individual, identifying each group of GPS trajectory points wherein the distance between the points is less than or equal to a prescribed distance threshold and the time interval between the points equals or exceeds a prescribed time period; and

for each identified group of GPS trajectory points,

computing the average latitude and average longitude of the group,

establishing an arrival time for the group which corresponds to the timestamp of the earliest GPS trajectory point in the group,

establishing a leaving time for the group which corresponds to the timestamp of the latest GPS trajectory point in the group, and

establishing a stay point for the group comprising the average latitude, average longitude, arrival time and leaving time of the group.

5. The process of claim 2, wherein the process action of generating the TBHG, comprises the actions of:

clustering the identified stay points into a hierarchically multi-level tree; and

constructing a graph on each level, said graph comprising directed edges each of which connects a pair of stay point clusters each of which has one of two consecutive stay points associated with an individual.

6. The process of claim 5, wherein the process action of clustering the identified stay points, comprises an action of using a density-based clustering technique to cluster the identified stay points.

7. The process of claim 5, wherein the process action of clustering the identified stay points, comprises the actions of:

performing an initial clustering the identified stay points;

filtering the initial stay point clusters to eliminate stay points from consideration that likely correspond to an individual'"'"'s home or workplace;

re-clustering the remaining identified stay points into a hierarchically multi-level tree

8. The process of claim 7, wherein the process action of filtering the initial stay point clusters, comprises the actions of:

for each individual and each cluster, determining a number of stay points associated with the that individual which are part of the cluster;

ascertaining if the number of stay points associated with the same individual in the same cluster exceeds a prescribed maximum number; and

whenever it is ascertained the number of stay points associated with the same individual in the same cluster exceeds the prescribed maximum number, eliminating those stay points from a cluster.

9. The process of claim 2, wherein the process action of identifying interesting locations in the region, comprises an action of employing a hypertext induced topic search (HITS)-based inference model to establish a relative interest of a visited location in the geospatial region of interest.

10. The process of claim 9, wherein the process action of employing a HITS-based inference model to establish the relative interest of a visited location in the geospatial region of interest, comprises an action of establishing a measure of the relative interest of the identified interesting locations at each of the plurality of geospatial levels of the TBHG, wherein said relative interest measure comprises a collection of authority scores generated based on an authority score of each geospatial region corresponding to the interesting location in ascendant levels of the TBHG, which are in turn based on hub scores associated with geospatial regions corresponding to the interesting locations in ascendant levels of the TBHG and which represent the degree of travel experience of an individual.

11. The process of claim 10, further comprising a process action of identifying users among the multiple individuals who traveled through the region that have a relatively higher degree of travel experience in the region than others of the individuals.

12. The process of claim 11, further comprising a process action of identifying commonly used travel sequences between the identified interesting locations in the geospatial region based on said multiple individuals'"'"' transition probabilities between locations.

13. The process of claim 12, wherein the process action of identifying commonly used travel sequences, comprises the process actions of:

computing a commonality score for possible location travel sequences, wherein the commonality score is based on the sum of hub scores of the individuals who have traveled the sequence and the authority scores associated with the locations contained in the sequence weighted by the transition probability of the individuals'"'"' movements; and

ranking the location travel sequences based on their commonality scores, with relatively higher scores indicating a more popular travel sequence.

14. The process of claim 13, wherein the process action of computing a commonality score for possible location travel sequences, comprises the actions of:

computing a commonality score for possible two location-length travel sequences in the geospatial region of interest; and

whenever a commonality score is generated for a travel sequence longer than two locations, computing the commonality score of the longer sequence by adding the commonality scores of the two location-length travel sequences making up the longer sequence.

15. The process of claim 14, wherein computing a commonality score for a two location-length travel sequence, comprises the actions of:

computing the sum of hub scores of the individuals who have traveled the sequence;

computing a first product of the authority score of the first location in the sequence and a weighting factor representing the probability of an individual moving out from the first location to the second location in the sequence;

computing a second product of the authority score of the second location in the sequence and a weighting factor representing the probability of an individual moving in to the first location from the second location in the sequence;

adding the first product to the second product and multiplying the resulting sum by the number of individuals who traveled from the first location to the second location to produce a third product;

adding the third product to the sum of hub scores of the individuals who have traveled the sequence to produce a final sum; and

designating the final sum to be the commonality score for the two location-length travel sequence.

16. A system for providing a listing of interesting locations in a geospatial region, comprising:

a general purpose computing device comprising a storage memory; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input location histories of multiple individuals comprising a log of periodically captured geospatial locations which were visited by one or more of the individuals in the geospatial region over a period of time,

extract stay points from the location histories, wherein a stay point is a geospatial position in said region which is within a prescribed maximum distance of locations where an individual spent a period of time exceeding a prescribed minimum period,

generate a tree-based hierarchical graph (TBHG) from the extracted stay points, wherein the TBHG models the multiple individuals'"'"' stay points as interesting locations on each of a plurality of scaled geospatial levels,

employ a hypertext induced topic search (HITS)-based inference model to establish a measure of the relative interest of the interesting locations in the geospatial region at each of the plurality of geospatial levels of the TBHG based on the number of individuals visiting the location weighted in terms of the travel experience of the individuals visiting the location, and

store a listing of the interesting locations in the geospatial region at each of the plurality of geospatial levels of the TBHG along with the measure of the relative interest established for the interesting locations.

17. The system of claim 16, further comprising program modules for:

receiving an input from a remote computing device having a display which specifies a particular geospatial region for which a listing of interesting locations is to be provided;

identifying the geospatial level of the TBHG most closely corresponding with the specified region, and

providing a listing of a prescribed number of top ranking interesting locations associated with the identified geospatial level of the TBHG to the remote computing device, wherein the top ranking interesting locations are ranked in accordance with their measure of the relative interest.

18. The system of claim 17, wherein:

the program module for receiving the input from the remote computing device specifying the particular geospatial region, comprises a sub-module for receiving the input in a form of data representing a map of the specified region, wherein a user of the remote device viewed and selected a map of a region of interest on the display of the remote computing device and transferred data representing a map to said general purpose computing device; and

the program module for providing the listing of the prescribed number of top ranking interesting locations, comprises a sub-module for providing the listing of top ranking interesting locations in a form of data representing a map which is displayable on the display of the remote computing device, and which when displayed highlights the location of each of the top ranking interesting locations at an appropriate place on the map.

19. The system of claim 17, further comprising program modules for:

identifying possible travel sequences between the interesting locations in the geospatial region at each of the plurality of geospatial levels of the TBHG;

computing a measure of the relative popularity of the possible travel sequences based on said multiple individuals'"'"' transition probabilities between the interesting locations;

storing the identified possible travel sequences along with the measure of their relative popularity computed for each of the sequences; and

whenever the listing of the prescribed number of top ranking interesting locations associated with the identified geospatial level of the TBHG is provided to the remote computing device, additionally providing a listing of a prescribed number of top ranking travel sequences between the top ranking interesting locations to the remote computing device, wherein said top ranking travel sequences are ranked in accordance with the measure of their relative popularity.

20. A computer-readable storage medium having computer-executable instructions stored thereon for identifying interesting locations and experienced travelers in a geospatial region, said computer-executable instructions comprising:

inputting location histories of multiple individuals comprising a log of periodically captured geospatial locations which were visited by one or more of the individuals in the geospatial region over a period of time;

extracting stay points from the location histories, wherein a stay point is a geospatial location in said region which is within a prescribed maximum distance of locations where an individual spent a period of time exceeding a prescribed minimum period;

generating a tree-based hierarchical graph (TBHG) from the identified stay points, wherein the TBHG models the multiple individuals'"'"' stay points as interesting locations on each of a plurality of scaled geospatial levels; and

employing a hypertext induced topic search (HITS)-based inference model to establish a measure of the relative interest of the interesting locations and a measure of the travel experience of each of the multiple individuals, in the geospatial region at each of the plurality of geospatial levels of the TBHG.