[미국특허]
Searching similar trajectories by locations
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G01C-021/00
G01C-021/34
G01C-021/26
G01C-021/36
출원번호
US-0794538
(2010-06-04)
등록번호
US-9593957
(2017-03-14)
발명자
/ 주소
Zheng, Yu
Chen, Zaiben
Xie, Xing
출원인 / 주소
Microsoft Technology Licensing, LLC
대리인 / 주소
Swain, Sandy
인용정보
피인용 횟수 :
2인용 특허 :
106
초록▼
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
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.
대표청구항▼
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
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, andconfigured 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; anddetermining 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; andcausing 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, andan 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; andremoving 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; andremoving 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; anda 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; andpruning 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; andcause 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, andan 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; andcalculate 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; andthe 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; andthe 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; andpruning 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; andcausing 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, andan 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; andcalculate 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; andadjusting 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; andproviding a travel route by using the trajectory from the location-based logs based at least in part on a highest calculated proximal similarity.
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는 부적절한 답변을 할 수 있습니다.