Route computation based on route-oriented vehicle trajectories
First Claim
1. A method implemented at least partially by a processor, the method comprising:
- collecting a sequence of global positioning system (GPS) points from route-oriented vehicle logs;
identifying geographical locations from the route-oriented vehicle logs, the geographical locations representing locations where route-oriented vehicles travelled as recorded in the vehicle logs;
extracting route-oriented vehicle trajectories from the route-oriented vehicle logs, the route-oriented vehicle trajectories representing individual trips; and
constructing a landmark graph based at least in part on the route-oriented vehicle trajectories by;
associating each route-oriented vehicle trajectory to a corresponding road segment;
determining a first frequency that a first road segment is visited by the route-oriented vehicles and at least a second frequency that other road segments are visited by the route-oriented vehicles, the first frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the first road segment, and the second frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the other road segments;
comparing the first frequency to the second frequency; and
identifying a landmark, the landmark being the first road segment when the first frequency is greater than the second frequency.
9 Assignments
0 Petitions
Accused Products
Abstract
Techniques for providing a route based on route-oriented vehicle trajectories are described. This disclosure describes receiving GPS logs and extracting route-oriented vehicle trajectory content from the GPS log data to pertain to a single trip. Next, the process maps each route-oriented vehicle trajectory to a corresponding road segment to construct a landmark graph. A landmark is a road segment frequently visited by route-oriented vehicles. The process includes receiving a user query with a starting point and a destination point; searching the landmark graph for a sequence of landmarks with corresponding transition times and a least amount of travel time. Then the process identifies and connects sets of road segments between each pair of consecutive landmarks, and displays a route to a user with a nearest landmark to the starting point, other landmarks along the route, and another nearest landmark to the destination point.
-
Citations
20 Claims
-
1. A method implemented at least partially by a processor, the method comprising:
-
collecting a sequence of global positioning system (GPS) points from route-oriented vehicle logs; identifying geographical locations from the route-oriented vehicle logs, the geographical locations representing locations where route-oriented vehicles travelled as recorded in the vehicle logs; extracting route-oriented vehicle trajectories from the route-oriented vehicle logs, the route-oriented vehicle trajectories representing individual trips; and constructing a landmark graph based at least in part on the route-oriented vehicle trajectories by; associating each route-oriented vehicle trajectory to a corresponding road segment; determining a first frequency that a first road segment is visited by the route-oriented vehicles and at least a second frequency that other road segments are visited by the route-oriented vehicles, the first frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the first road segment, and the second frequency being determined based on a number of the route-oriented vehicle trajectories that are associated with the other road segments; comparing the first frequency to the second frequency; and identifying a landmark, the landmark being the first road segment when the first frequency is greater than the second frequency. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. One or more computer-readable media encoded with instructions that, when executed by a processor, perform acts comprising:
-
presenting a user interface on a display of a portable electronic device, the user interface to access a service application that provides map-based services; receiving user input to the user interface indicating a starting location and a destination location; accessing a landmark graph constructed from route-oriented vehicle trajectories, a landmark being identified when a first frequency of route-oriented vehicles visiting a road segment is compared to a second frequency of route-oriented vehicles visiting a second or subsequent road segment and the first frequency is greater than the second frequency; computing an initial path, based on the starting location and the destination location, between each pair of consecutive landmarks of the initial path; and refining the initial path by finding a route that sequentially connects the landmarks, from the starting location to the destination location. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
16. A system comprising:
-
a memory; one or more processors coupled to the memory having instructions to perform acts comprising; receiving user input indicating a starting location, a destination location, and a time of day and a category of day; accessing a landmark graph stored in a database, the landmark graph identifying landmarks on the landmark graph, landmarks being identified as road segments having a threshold frequency of visits by a variety of vehicles, the threshold frequency being greater than the frequency of visits by a variety of vehicles on other road segments; searching the landmark graph for an initial route based on a sequence of landmarks and a least amount of travel time based at least in part on the starting location and the destination location; calculating an initial path between each pair of consecutive landmarks of the initial route; and presenting the initial route with nearest landmark to the starting location, landmarks along the route, and another nearest landmark to the destination location for the time of day and the category of day as specified. - View Dependent Claims (17, 18, 19, 20)
-
Specification