Searching similar trajectories by locations

• US 9,593,957 B2
• Filed: 06/04/2010
• Issued: 03/14/2017
• 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): Zeender, Ryan
• Assistant Examiner(s): BUCHANAN, CHRISTOPHER R
• Application Number:
  US12/794,538
• Publication Number:
  US 20110301832A1
• Time in Patent Office: 2,475 Days
• Field of Search: 701/200, 701/400, 701/410
• US Class Current: 1/1
• 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 from user devices associated with GPS sensors;

accessing, from a database storing the GPS logs, a first trajectory having a plurality of points, wherein an individual point in the plurality of points identifies a geographic location previously visited by a first user with a first user device of the user devices;

generating a first user interface to provide functionality for a second user;

causing the first user interface to be presented to the second user via a display of a second user device of the user devices associated with the second user, the first user interface;

including a first map illustrating the geographic location, and

configured to receive input from the second user;

receiving a set of desired geographical locations from the second user via the first user interface, the first map illustrating at least one location of the set of desired geographical locations;

receiving a request for a second trajectory associated with the set of desired geographical locations;

determining that the first trajectory is a candidate trajectory based at least in part on;

calculating, by the processor, a spatial distance between an individual point of the plurality of points and a desired geographical location of the set of desired geographical locations;

calculating, by the processor and based at least in part on applying a similarity function to at least the spatial distance, a proximal similarity between the first trajectory and the set of desired geographical locations; and

determining that the proximal similarity is less than a predetermined threshold;

accessing additional trajectories to create a set of candidate trajectories for determining the second trajectory, wherein the set of candidate trajectories includes the first trajectory;

removing unqualified candidate trajectories from the set of candidate trajectories based at least in part on proximal similarities determined between the set of desired geographical locations and individual unqualified candidate trajectories of the unqualified candidate trajectories, wherein resulting candidate trajectories comprise a refined set of candidate trajectories;

identifying the second trajectory from the refined set of candidate trajectories, wherein the second trajectory is determined based at least in part on a latitude of the desired geographical location determined by a GPS sensor of the first user device, and a longitude of the desired geographical location determined by the GPS sensor;

generating a second user interface to provide functionality for presenting the second trajectory to the second user; and

causing the second user interface to be presented to the second user via the display of the second user device, the second user interface including a second map illustrating;

the set of desired geographical locations,

the second trajectory connecting each location of the set of desired geographical locations, and

an ordered travel sequence corresponding to the second trajectory.

2. The method of claim 1, wherein receiving the request for the second trajectory is based at least in part on the second user selecting each of the desired geographical locations of the set of desired geographical locations on the first map.

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

4. The method of claim 1, wherein removing the unqualified candidate trajectories comprises:

computing a lower bound of proximal similarity for individual candidate trajectories in the set of the candidate trajectories;

computing an upper bound of proximal similarity for candidate trajectories that are external to the set of the candidate trajectories; and

removing the unqualified candidate trajectories based at least in part on the lower bound of proximal similarity and the upper bound of proximal similarity.

5. The method of claim 1, wherein identifying the second trajectory is based at least in part on receiving another request specifying an order of travel for the set of desired geographical locations.

6. The method of claim 1, wherein identifying the second trajectory is based at least in part on historical data of a travel sequence of the second user.

7. The method of claim 1, wherein the removing unqualified candidate trajectories from the set of candidate trajectories is further based at least in part on an incremental based k-nearest neighbor analysis.

8. The method of claim 7, wherein removing the unqualified candidate trajectories from the set of candidate trajectories based at least in part on the incremental based k-nearest neighbor analysis comprises:

indexing individual points in individual candidate trajectories of the set of candidate trajectories in a spatial index;

determining that at least one individual point of the individual points associated with an individual candidate trajectory of the set of candidate trajectories in the spatial index is outside of a threshold distance from individual desired geographical locations of the set of desired geographical locations; and

removing the individual candidate trajectory of the set of candidate trajectories.

9. The method of claim 1, wherein identifying the ordered travel sequence is based at least in part on at least one of bus routes, traffic flow patterns on one way streets, or traffic flow.

10. The method of claim 1, wherein the second trajectory is determined based at least in part on a time associated with the first user device being located at the desired geographical location determined by the GPS sensor.

11. The method of claim 1, wherein the second trajectory is determined based at least in part on respective latitudes and longitudes of each geographical location in the set of desired geographical locations, the respective latitudes and longitudes being determined by at least one of the GPS sensors.

12. The method of claim 8, wherein the indexing the individual points in the individual candidate trajectories comprises indexing the individual points in a rectangle-tree (R-tree).

13. A system comprising:

a processor;

a memory coupled to the processor and storing;

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

a trajectory route model module to;

receive location-based logs that are received from global position system (GPS) sensors associated with individual user devices;

access individual location-based logs of the location-based logs from a database storing the location-based logs;

generate a first user interface;

cause the first user interface to be displayed via a display of an individual user device of the first user, the first user interface including a first map configured to receive input from the first user;

receive the input specifying the first set of geographical locations from the first user via the first user interface, the first map illustrating at least one location of the first set of geographical locations;

determine trajectories connecting a second set of geographical locations, wherein the second set of geographical locations were previously visited by a second user with an additional user device including a GPS sensor;

determine, based at least in part on a similarity function, a proximal similarity between a first individual geographical location of the first set of geographical locations and a second individual geographical location from the location-based logs, wherein the location-based logs include a latitude of the second individual geographical location determined by the GPS sensor of the additional user device, and a longitude of the second individual geographical location determined by the GPS sensor;

determine a plurality of initial paths, individual initial paths of the plurality of initial paths connecting the first set of geographical locations based at least in part on the proximal similarity;

refine the plurality of initial paths based at least in part on the proximal similarity, the refining comprising;

arranging coordinates associated with individual geographical locations of the second set of geographical locations into a spatial index;

based at least in part on the spatial index, creating a candidate set of trajectories from the plurality of initial paths, the candidate set of trajectories including at least the first individual geographical location of the first set of geographical locations; and

pruning unqualified candidate trajectories from the candidate set of trajectories to form a refined set of candidate trajectories based at least in part on determining that proximal similarities associated with the unqualified candidate trajectories are above a predetermined threshold;

identify a particular trajectory from the refined set of candidate trajectories, wherein the particular trajectory is determined based at least in part on the latitude and the longitude;

generate a second user interface; and

cause the second user interface to be displayed via the display of the individual user device of the first user, the second user interface including a second map illustrating;

the first set of geographical locations,

the particular trajectory connecting each location of the first set of geographical locations, and

an ordered travel sequence corresponding to the particular trajectory.

14. The system of claim 13, wherein the determining the individual initial paths comprises using a k-nearest neighbor (k-NN) algorithm to:

identify a subset of trajectories from the location-based logs that are closest to a geographical location of the first set of geographical locations based at least in part on searching the location-based logs using a k-nearest neighbor (k-NN) search;

calculate a lower bound of proximal similarity for a particular trajectory in the subset of trajectories that is closest in distance to the first set of geographical locations; and

calculate an upper bound of proximal similarity for a particular trajectory in the subset of trajectories that is not identified in the subset of trajectories.

15. The system of claim 13, wherein:

the trajectory route application module is further configured to receive another input specifying an order of travel for the first set of geographical locations; and

the trajectory route application module is further configured to adjust the individual initial paths by connecting the first set of geographical locations based at least in part on the order of travel.

16. The system of claim 13, wherein:

the trajectory route model module is further configured to refine the plurality of initial paths by finding a trajectory from the location-based logs that sequentially connects the geographical locations of the first set of geographical locations; and

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

17. One or more computer storage devices storing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

generating a first user interface;

causing the first user interface to be displayed via a display of an individual user device of a first user, the first user interface including a first map configured to receive input from the first user;

receiving input from the first user, via the first user interface, specifying a first set of geographical locations of interest to a first user, the first map illustrating at least one location of the first set of geographical locations;

accessing location-based logs from a database storing the location-based logs, wherein the location-based logs are received from individual user devices associated with global position system (GPS) sensors and include trajectories connecting a second set of geographical locations previously visited by a second user with an additional user device including a GPS sensor;

computing a path connecting the first set of geographical locations based at least in part on calculating a proximal similarity between a first individual geographical location of the first set of geographical locations and a second individual geographical location of the second set of geographical locations, wherein the location-based logs include a latitude of the second individual geographical location determined the GPS sensor of the additional user device, and a longitude of the second individual geographical location determined by the GPS sensor, the computing comprising;

indexing GPS location information associated with the second set of geographical locations into a spatial index;

based at least in part on the indexing, creating a candidate set of trajectories from the location-based logs, the candidate set of trajectories from the location-based logs including at least the first individual geographical location of the first set of geographical locations; and

pruning unqualified candidate trajectories from the candidate set of trajectories to form a refined set of candidate trajectories based at least in part on determining that proximal similarities associated with the unqualified candidate trajectories are above a predetermined threshold;

identifying a particular trajectory from the refined set of candidate trajectories, wherein the particular trajectory is determined based at least in part on the latitude and the longitude;

generating a second user interface; and

causing the second user interface to be displayed via the display of the individual user device of the first user, the second user interface including a second map illustrating;

the first set of geographical locations,

the particular trajectory connecting each location of the first set of geographical locations, and

an ordered travel sequence corresponding to the particular trajectory.

18. The one or more computer storage devices of claim 17, wherein the computing the path comprises using a k-nearest neighbor (k-NN) algorithm to:

identify a subset of trajectories from the candidate set that are closest to a geographical location of the first set of geographical locations based at least in part on searching the spatial index using a k-nearest neighbor (k-NN) search;

calculate a lower bound of proximal similarity for a particular trajectory in the subset of trajectories that is closest in distance to the first set of geographical locations; and

calculate an upper bound of proximal similarity for a particular trajectory in the subset of trajectories that is not identified in the subset of trajectories.

19. The one or more computer storage devices of claim 17, wherein the operations further comprise:

receiving another input specifying an order of travel for the first set of geographical locations; and

adjusting the path by connecting the first set of geographical locations in the order of travel specified by the user.

20. The one or more computer storage devices of claim 17, wherein the operations further comprise:

refining the path by determining a trajectory from the location-based logs that sequentially connects geographical locations included in the first set of geographical locations; and

providing a travel route by using the trajectory from the location-based logs based at least in part on a highest calculated proximal similarity.