Searching Similar Trajectories by Locations

• US 20110301832A1
• Filed: 06/04/2010
• Published: 12/08/2011
• Est. Priority Date: 06/04/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zheng, Yu, Xie, Xing, Chen, Zaiben
• Granted Patent: US 9,593,957 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G01C 21/3667 Display of a road map G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

Techniques for providing a trajectory route to multiple geographical locations of interest are described. This disclosure describes receiving global position system (GPS) logs associated with respective individual devices, each of the GPS logs including trajectories connecting a set of geographical locations previously visited by an individual of a respective individual device. A trajectory route service receives a request for a trajectory connecting a set of geographical locations of interest specified by a user. The trajectory route service calculates a proximal similarity between (1) the set of geographical locations of interest specified by the user, and (2) respective sets of geographical locations from the GPS logs. The trajectory route service constructs the requested trajectory with use of at least one of the trajectories from the GPS logs determined at least in part according to the calculated proximal similarities.

Claims

1. A method implemented at least partially by a processor, the method comprising:

receiving global position system (GPS) logs associated with respective user devices, each of the GPS logs including trajectories connecting a set of geographical locations previously visited by a user of a respective user device;

receiving a request for a trajectory connecting a set of geographical locations of interest specified by the user;

calculating a proximal similarity between (1) the set of geographical locations of interest specified by the user, and (2) respective sets of geographical locations from the GPS logs; and

constructing the requested trajectory with use of at least one of the trajectories from the GPS logs determined at least in part according to the calculated proximal similarities.

2. The method of claim 1, wherein the receiving the request comprises presenting a map of geographical locations to the user, wherein the user requests the set of geographical locations by selecting each geographical location of interest on the map.

3. The method of claim 1, wherein the set of geographical locations specified by the user is approximately ten or less geographical locations.

4. The method of claim 1, wherein the at least one trajectory from the GPS logs is determined based on the at least one trajectory connecting a set of geographical locations from the GPS logs having a highest calculated proximal similarity to the set of geographical locations of interest specified by the user.

5. The method of claim 1, further comprising:

indexing points in the trajectories from the GPS logs in a rectangle-tree (R-tree), wherein the points represent the geographical locations previously visited by the user of the respective user device; and

searching for the points in the trajectories from the GPS logs that are within a threshold distance of the set of geographical locations of interest specified by the user.

6. The method of claim 1, further comprising:

computing a distance from a point on each trajectory of a candidate set of the trajectories included in the GPS logs to at least the geographical location of interest specified by the user; and

identifying a subset of trajectories from the candidate set that is matched to the at least the geographical location of interest specified by the user having a smallest measured distance from the point on the trajectory in the candidate set to the geographical location of interest specified by the user.

7. The method of claim 1, further comprising:

creating a candidate set of trajectories from the GPS logs, the candidate set of trajectories from the GPS logs include at least a geographical location of interest specified by the user;

computing a lower bound of the proximal similarity for each trajectory candidate in the candidate set of trajectories from the GPS logs;

computing an upper bound of the proximal similarity for the trajectories that are not identified in the candidate set; and

pruning unqualified trajectories based at least in part on results from the lower bound and the upper bound of the proximal similarity.

8. The method of claim 1, further comprising:

determining whether a distance from the trajectory from the GPS logs to each of the geographical locations of interest specified by the user is greater than or less than a predetermined threshold distance;

in an event that the distance is greater than the predetermined threshold distance, refraining from using the trajectory when constructing the requested trajectory; and

in an event that the distance is less than the predetermined threshold distance, using the trajectory when constructing the requested trajectory.

9. The method of claim 1, further comprising:

receiving another request specifying an order of travel for the set of geographical locations of interest specified by the user; and

adjusting the trajectories identified for the requested trajectory by connecting the trajectories in the order of travel for the set of geographical locations of interest specified by the user.

10. One or more computer-readable storage media encoded with instructions that, when executed by a processor, perform acts comprising:

accessing a trajectory map constructed from global position system (GPS) logs associated with respective individual devices, each of the GPS logs include trajectories that connect a set of geographical locations previously visited by an individual of a respective individual device;

receiving a request for a travel route to multiple geographical locations of interest specified by a user;

computing an initial path based on connecting the set of multiple geographical locations of interest to the user at least in part on searching the trajectories from the GPS logs for trajectories that are closest in distance to each of the multiple geographical locations of interest;

refining the initial path by finding a trajectory from the GPS logs that sequentially connects each of the multiple geographical locations of interest; and

providing the travel route by using the trajectory from the GPS logs that is closest in distance and sequentially connects each of the multiple geographical locations of interest.

11. The computer-readable storage media of claim 10, wherein the multiple geographical locations of interest are identified by a street address, a name of an attraction, a building name, a type of a location, a highway, a beach, a school, an arena, or a stadium.

12. The computer-readable storage media of claim 10, wherein the travel route illustrates a sequence of travel based at least in part on a historical travel sequence of the geographical locations previously visited by the user.

13. The computer-readable storage media of claim 10, wherein the searching the trajectories from the GPS logs comprises:

retrieving trajectory points from the GPS logs that are within a threshold distance to each of the multiple geographical locations of interest specified by the user, a trajectory point represents a geographical location previously visited by a user of a respective user device;

identifying the retrieved trajectory points that are within an intersection of the multiple geographical locations specified by the user; and

determining the trajectory points that are within the intersection as being closest in distance to the multiple geographical locations of interest specified by the user.

14. The computer-readable storage media of claim 10, wherein the computing the initial path comprises using a k−

nearest neighbor (k−

NN) algorithm to;

identify a subset of trajectories from the GPS logs that include the trajectories being closest to a geographical location based at least in part on the searching using a k−

nearest neighbor (k−

NN) search;

calculate a lower bound of a similarity search for each trajectory in the subset being closest in distance to the multiple geographical locations of interest; and

calculate an upper bound of the similarity search for the trajectories that are not identified in the subset of trajectories.

15. The computer-readable storage media of claim 10, wherein the refining the initial path comprises:

identifying a subset of trajectories from the GPS logs that include the trajectories being closest to a geographical location of interest specified by the user based at least in part on the searching using a k−

nearest neighbor (k−

NN) search;

computing an upper bound of a similarity function for the subset of trajectories from the GPS logs;

sorting the trajectories in the subset in a descending order when a minimum similarity function is equal to or greater than the upper bound of a next candidate in the subset; and

identifying the trajectories from the subset to be used in constructing the trajectory for the travel route.

16. The computer-readable storage media of claim 10, further comprising:

receiving another request specifying an order of travel for the multiple geographical locations of interest;

adjusting trajectory points for the travel route to match the order of travel; and

presenting an ordered trajectory route by sequentially connecting the multiple geographical locations of interest in the order of travel specified by the user.

17. A system comprising:

a processor;

a memory coupled to the processor and storing;

a trajectory route application module to receive input specifying a set of geographical locations of interest to a user; and

a trajectory route model module to construct a model based on location-based logs associated with respective individual user devices, the logs include trajectories connecting a set of geographical locations previously visited by an individual user of a respective individual user device;

the trajectory route model module to compute an initial path connecting the set of geographical locations of interest to the user based at least in part on calculating a proximal similarity between the set of geographical locations of interest to the user and respective sets of geographical locations from the location-based logs.

18. The system of claim 17, wherein the computing the initial path comprises using a k−

nearest neighbor (k−

NN) algorithm to;

identify a subset of trajectories from the location-based logs that include the trajectories being closest to a geographical location based at least in part on searching the location-based logs using a k−

nearest neighbor (k−

NN) search;

calculate a lower bound of the proximal similarity for each trajectory in the subset of trajectories being closest in distance to the set of geographical locations of interest; and

calculate an upper bound of the proximal similarity for the trajectories that are not identified in the subset of trajectories.

19. The system of claim 17, wherein:

the trajectory route application module is further to receive another request specifying an order of travel for the set of geographical locations of interest to the user; and

the trajectory route application module is further to adjust the initial path by connecting the set of geographical locations in the order of travel specified by the user.

20. The system of claim 17, wherein:

the trajectory route model module is further to refine the initial path by finding a trajectory from the location-based logs that sequentially connects each of the geographical locations of interest; and

the trajectory route model module is further to provide a travel route by using the trajectory from the location-based logs based at least in part on a highest calculated proximal similarity.