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.