[미국특허]
Route computation based on route-oriented vehicle trajectories
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G01C-021/36
G01S-019/42
G06F-017/30
G01C-021/34
출원번호
US-0712053
(2010-02-24)
등록번호
US-9261376
(2016-02-16)
발명자
/ 주소
Zheng, Yu
Lou, Yin
Zhang, Chengyang
Xie, Xing
출원인 / 주소
MICROSOFT TECHNOLOGY LICENSING, LLC
대리인 / 주소
Swain, Sandy
인용정보
피인용 횟수 :
11인용 특허 :
105
초록▼
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 tra
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.
대표청구항▼
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 location
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; andconstructing 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; andidentifying a landmark, the landmark being the first road segment when the first frequency is greater than the second frequency. 2. The method of claim 1, wherein the first road segment is a directed edge that is associated with a direction symbol, two terminal points, and a list of intermediate points describing the road segment with a polyline. 3. The method of claim 1, further comprising: determining whether a time interval between two consecutive GPS points meets or exceeds a predetermined threshold; andpartitioning the two consecutive GPS points into two different trajectories based on whether the time interval between the two consecutive GPS points meets or exceeds the threshold. 4. The method of claim 1, further comprising dividing the route-oriented vehicle trajectories into separate trajectories when a stay point is identified, the stay point representing a geographical region in which a route-oriented vehicle remained within a threshold distance for a threshold time period. 5. The method of claim 1, wherein the associating each route-oriented vehicle trajectory to a corresponding road segment comprises: identifying candidate road segments and correlating the candidate road segments to candidate projection points;detecting the candidate projection points on candidate edges;identifying a probability that a GPS point matches a candidate point computed based on a distance between two points;identifying a list of road segments based on determining a shortest path from a first candidate projection point to a second candidate projection point;generating a candidate graph for the route-oriented vehicle trajectory with a set of candidate projection points and a set of edges to represent the shortest paths between neighboring candidate points; anddetermining a road segment that matches the trajectory. 6. The method of claim 1, wherein the constructing the landmark graph further comprises: computing a number of route-oriented vehicle trajectories that connect any of the landmarks; andconnecting the landmarks with a landmark edge when there is at least a subset of the route-oriented vehicle trajectories passing through the landmarks, the landmark edge to represent travels between the landmarks by the route-oriented vehicles. 7. The method of claim 1, further comprising: determining a median time cost for travelling on a landmark edge, the landmark edge to connect one landmark to another landmark. 8. The method of claim 1, further comprising: receiving a user query with a starting point and a destination point for directions;searching the landmark graph for an initial route that is represented by a sequence of landmarks with corresponding transition times and a least amount of travel time;computing a set of connected road segments between each pair of consecutive landmarks of an initial route; andproviding data indicating a route including the directions with landmarks from the starting point to the destination point. 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; andrefining the initial path by finding a route that sequentially connects the landmarks, from the starting location to the destination location. 10. The computer-readable media of claim 9, in response to the initial path, further comprising: calculating additional paths from the starting location to each terminal point of the landmarks on the initial path; anddetermining the additional paths for unidirectional and bidirectional road segments. 11. The computer-readable media of claim 9, further comprising: searching the landmark graph for the initial path based on a sequence of landmarks with corresponding transition times between the landmarks and a least amount of travel time; andvisually presenting the route to a user, the route illustrating a nearest landmark to the starting location, any landmarks along the route, and another nearest landmark to the destination location. 12. The computer-readable media of claim 9, further comprising: collecting the route-oriented vehicle logs that include a sequence of global positioning system (GPS) points from the variety of route-oriented vehicles;determining geographical locations from the route-oriented vehicle logs, the geographical locations to represent regions where the variety of route-oriented vehicles have travelled as recorded in the vehicle logs; andsegmenting the geographical locations into the road segments, a road segment including a directed edge that is associated with a direction symbol, two terminal points, and a list of intermediate points describing the road segment with a polyline. 13. The computer-readable media of claim 9, further comprising: extracting route-oriented vehicle trajectories from route-oriented vehicle logs, the route-oriented vehicle logs are represented with a sequence of global positioning system (GPS) points from the variety of route-oriented vehicles engaged in business related transportation;representing individual trips based on a sequence of road segments with transition times with route-oriented vehicle trajectories;determining when a time interval between two consecutive GPS points is greater than or less than a predetermined threshold: in an event that the time interval between two consecutive GPS points is greater the predetermined threshold, partition the two consecutive GPS points into two different trajectories; orin an event that the time interval between the two consecutive GPS points is less than the predetermined threshold, use the two consecutive GPS points in a trajectory. 14. The computer-readable media of claim 9, further comprising determining when to partition route-oriented vehicle logs into the route-oriented vehicle trajectories based on a stay point, the stay point represents a geographical region in which the route-oriented vehicle remained within a threshold distance for a threshold time period. 15. The computer-readable media of claim 9, further comprising constructing the landmark graph based at least in part on the route-oriented vehicle trajectories by: matching each route-oriented vehicle trajectory to a corresponding road segment;representing the landmark as a vertex on the landmark graph; andconnecting at least two vertices with a landmark edge, the landmark edge to represent travels between the at least two vertices by at least a subset of the variety of route-oriented vehicles by a number of times greater than a threshold. 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; andpresenting 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. 17. The system of claim 16, further comprising: collecting vehicle logs, which include a sequence of global positioning system (GPS) points from the variety of vehicles;extracting vehicle trajectories from the vehicle logs, the vehicle trajectories representing individual trips made by the variety of vehicles;partitioning the vehicle trajectories made by the variety of vehicles into multiple partitions according to times of day and categories of days; andgenerating landmark graphs of landmarks for each of the multiple partitions, wherein the accessing accesses the landmark graph associated with the time of day and the category of day. 18. The system of claim 16, further comprising partitioning the vehicle trajectories into multiple parts based on a time of a day and a category of day. 19. The system of claim 16, further comprising computing paths between each pair of consecutive landmarks of the initial route, a path is a set of connected road segments. 20. The system of claim 16, further comprising: associating each vehicle trajectory to a corresponding road segment; andspecifying a road segment visited at a greater frequency relative to another road segment as a landmark, the greater frequency being determined based on a number of vehicle logs for the landmark.
Letchner, Julia M.; Krumm, John C.; Horvitz, Eric J., Collaborative route planning for generating personalized and context-sensitive routing recommendations.
Dunk, Craig A., Data transfer from a host server via a tunnel server to a wireless device, and associating a temporary IPV6 address with a temporary IPV4 address for communicating in an IPV4 wireless network with the device.
Kan,Gene H.; Faybishenko,Yaroslav; Cutting,Douglass R.; Camarda,Thomas J.; Doolin,David M.; Waterhouse,Steve, Distributed information discovery through searching selected registered information providers.
Isozaki, Hiroshi; Kokubo, Takashi; Kanazawa, Koji, Information processing apparatus, information processing method, and information processing program.
Partridge, Kurt E.; Price, Robert R.; Ducheneaut, Nicolas B., Method and apparatus for automatically incorporating hypothetical context information into recommendation queries.
Apte, Chidanand; Dong, Jin; Li, Ta-Hsin; Xie, Ming; Yin, Wen Jun; Zhang, Bin; Zhu, Ming H., Method and apparatus for location evaluation and site selection.
Christopher Kenneth Hoover Wilson ; Seth Olds Rogers ; Patrick Wyatt Langley, Method and system for autonomously developing or augmenting geographical databases by mining uncoordinated probe data.
Frederick D. Busche ; Alexander Darius Zekulin, Method and system for integrating spatial analysis and data mining analysis to ascertain relationships between collected samples and geology with remotely sensed data.
Frederick Davis Busche, Method and system for integrating spatial analysis, and scheduling to efficiently schedule and monitor infrastructure maintenance.
Ahuja, Abha; Ayers, Matt; Black, Ben; Brown, Chris; Cohn, Daniel T.; Ramsey, Stephen; Ronen, Ophir; Schachter, Paul J.; Stiffelman, Oscar B.; Wheeler, Christopher D., Method and system for optimizing routing through multiple available internet route providers.
Gottfurcht, Elliot A.; Gottfurcht, Grant E.; Dunn, Shawn C., Method and system of providing credit card user with barcode purchase data and recommendation automatically on their personal computer.
Frias Martinez, Enrique; Frias Martinez, Vanessa; Vieira, Marcos; Oliver, Nuria, Method for an automatic identification of urban dense areas from cell phones records.
Emens, Michael L.; Ford, Daniel A.; Kraft, Reiner; Tewari, Gaurav, Method of automatically selecting a mirror server for web-based client-host interaction.
Hopkins, Karen A.; McGrath, Suzanne M.; Bauer, Ellen M.; Bennett, James R.; Borak, Jason M.; Devries, Steven P.; Herbst, James M., Method of collecting information for a geographic database for use with a navigation system.
Nicol,John Raymond; Martin,Christopher Michael; Paschetto,James Edward; Wittenburg,Kent Barrows, Methods and systems for selection of multimedia presentations.
McMenimen, James L.; Campbell, Christopher J.; Ruble, Barbara K.; Fabian, Willa M.; Clark, Larry G.; Thompson, David L., Responsive manufacturing and inventory control.
Fuh Gene Y. C. ; Dessloch Stefan ; Lee Daniel Tsunfang ; Li Ping ; Mattos Nelson Mendonca ; Talmoud Shahrokh ; Wang Yun, Supporting database indexes based on a generalized B-tree index.
Israni,Vijaya S.; Ashby,Richard A.; Bouzide,Paul M.; Jasper,John C.; Fernekes,Robert P.; Nyczak,Gregory M.; Smith,Nicholas E.; Lampert,David S.; Meek,James A.; Crane,Aaron I., System and method for use and storage of geographic data on physical media.
Anderson, IV,Charles Edward; Willis, Jr.,Thomas Carroll; Willis,Jason Andrew, System, method and computer program product for caching domain name system information on a network gateway.
Chen,Ying; Rao,Fang Yan; Stolze,Knut, Systems, methods, and computer program products to reduce computer processing in grid cell size determination for indexing of multidimensional databases.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.