Searching similar trajectories by locations

• US 10,571,288 B2
• Filed: 01/20/2017
• Issued: 02/25/2020
• Est. Priority Date: 06/04/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zheng, Yu, Chen, Zaiben, Xie, Xing
• Primary Examiner(s): Ramesh, Krishnan
• Application Number:
  US15/411,852
• Publication Number:
  US 20170131110A1
• Time in Patent Office: 1,131 Days
• Field of Search: 701424
• 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. One or more non-transitory computer-readable storage media encoded with instructions that, when executed by a processor, perform acts comprising:

receiving global position system (GPS) logs associated with respective individual devices, individual ones of the GPS logs including trajectories that connect a set of geographical locations previously visited by an individual of a respective individual device, the GPS logs having been received from GPS sensors associated with the respective individual devices;

accessing a trajectory map constructed from the GPS logs;

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

determining a trajectory that sequentially connects each of the multiple geographical locations and is within a threshold distance of at least one of the multiple geographical locations based at least in part on;

applying a similarity function to the multiple geographical locations and the trajectories in the trajectory map, wherein the similarity function assesses similarity of the multiple geographical locations to geographic locations used in deriving the trajectories;

determining a plurality of trajectories that have respective proximal similarities to the multiple geographical locations that are less than a predetermined threshold; and

determining an individual trajectory of the plurality of trajectories that sequentially connects the multiple geographical locations, the individual trajectory corresponding to the trajectory; and

providing, as a response to the request for the travel route, the trajectory to a device associated with the user.

2. The computer-readable storage media of claim 1, wherein the multiple geographical locations of interest are identified by at least one of 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.

3. The computer-readable storage media of claim 1, wherein determining the trajectory further comprises using a k-nearest neighbor (k-NN) algorithm to determine that the individual trajectory is a closest trajectory to at least one geographical location of the multiple geographical locations based at least in part on searching the plurality of trajectories using a k-nearest neighbor (k-NN) search.

4. The computer-readable storage media of claim 1, the acts further comprising:

receiving another request specifying an order for visiting the multiple geographical locations; and

determining that the individual trajectory sequentially connects the multiple geographical locations in the order.

5. The computer-readable storage media of claim 1, the acts further comprising:

presenting a dynamic user interface via the device associated with the user, the dynamic user interface configured to enable the user to select the multiple geographical locations of interest;

receiving an indication of a selection of the multiple geographical locations of interest via the dynamic user interface; and

receiving the request for the travel route to the multiple geographical locations based at least in part on the indication.

6. The computer-readable storage media of claim 5, wherein the dynamic user interface comprises a map.

7. The computer-readable storage media of claim 1, the acts further comprising determining a subset of the plurality of trajectories based at least in part on searching the plurality of trajectories, the searching comprising:

identifying individual trajectories of the plurality of trajectories that are within an intersection of the multiple geographical locations; and

determining one or more individual trajectories that are closest in distance to the multiple geographical locations, the one or more individual trajectories comprising the subset.

8. The computer-readable storage media of claim 7, the acts further comprising determining the individual trajectory from the subset.

9. The computer-readable storage media of claim 1, the acts further comprising:

computing a lower bound of proximal similarity for first individual trajectories of the plurality of trajectories;

computing an upper bound of proximal similarity for second individual trajectories that are external to the plurality of trajectories;

removing one or more trajectories of the plurality of trajectories based at least in part on the lower bound and upper bound to generate a refined set of trajectories; and

determining the individual trajectory from the refined set of trajectories.

10. A computer-implemented method comprising:

receiving global position system (GPS) logs associated with respective individual devices, individual ones of the GPS logs including trajectories that connect a set of geographical locations previously visited by an individual of a respective individual device, the GPS logs having been received from GPS sensors associated with the respective individual devices;

accessing a trajectory map constructed from the GPS logs;

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

determining a trajectory that sequentially connects each of the multiple geographical locations and is within a threshold distance of at least one of the multiple geographical locations based at least in part on;

applying a similarity function to the multiple geographical locations and the trajectories in the trajectory map, wherein the similarity function assesses similarity of the multiple geographical locations to geographic locations used in deriving the trajectories;

determining a plurality of trajectories that have respective proximal similarities to the multiple geographical locations that are less than a predetermined threshold; and

determining an individual trajectory of the plurality of trajectories sequentially connects the multiple geographical locations, the individual trajectory corresponding to the trajectory; and

providing the trajectory to a device associated with the user.

11. The computer-implemented method of claim 10, further comprising determining a subset of the plurality of trajectories based at least in part on searching the plurality of trajectories, the searching comprising:

identifying individual trajectories of the plurality of trajectories that are within an intersection of the multiple geographical locations; and

determining one or more individual trajectories are closest in distance to the multiple geographical locations, the one or more individual trajectories comprising the subset.

12. The computer-implemented method of claim 11, further comprising determining the individual trajectory from the subset.