[미국특허]
Determine spatiotemporal causal interactions in data
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06K-009/00
G08G-001/01
G06K-009/46
G06F-019/00
출원번호
US-0587270
(2014-12-31)
등록번호
US-9536146
(2017-01-03)
발명자
/ 주소
Zheng, Yu
Xie, Xing
출원인 / 주소
Microsoft Technology Licensing, LLC
대리인 / 주소
Swain, Sandy
인용정보
피인용 횟수 :
2인용 특허 :
106
초록▼
Techniques for detecting outliers in data and determining spatiotemporal causal interactions in the data are discussed. A process collects global positioning system (GPS) points in logs and identifies geographical locations to represent the area where the service vehicles travelled with a passenger.
Techniques for detecting outliers in data and determining spatiotemporal causal interactions in the data are discussed. A process collects global positioning system (GPS) points in logs and identifies geographical locations to represent the area where the service vehicles travelled with a passenger. The process models traffic patterns by: partitioning the area into regions, segmenting the GPS points from the logs into time bins, and identifying the GPS points associated with transporting the passenger. The process projects the identified GPS points onto the regions to construct links connecting GPS points located in two or more regions. Furthermore, the process builds a three-dimensional unit cube to represent features of each link. The points farthest away from a center of data cluster are detected as outliers, which represent abnormal traffic patterns. The process constructs outlier trees to evaluate relationships of the outliers and determines the spatiotemporal causal interactions in the data.
대표청구항▼
1. A method implemented at least partially by a processor, the method comprising: accessing, from a database associated with a content service provider, logs of global positioning system (GPS) points collected by geolocation sensors associated with service vehicles;identifying geographical locations
1. A method implemented at least partially by a processor, the method comprising: accessing, from a database associated with a content service provider, logs of global positioning system (GPS) points collected by geolocation sensors associated with service vehicles;identifying geographical locations from the GPS points to represent an area where the service vehicles travelled as recorded in the logs;generating a graph of regions associated with the area based at least in part on the logs associated with the area in a plurality of time frames;detecting outliers in the GPS points based at least in part on the graph; andproviding, via a user interface that is presented via a display of a device, recommendations for travelling in the area based at least in part on the outliers. 2. The method of claim 1, further comprising: dividing the area into the two or more regions based at least in part on major roads; andgenerating links for connecting pairs of regions of the two or more regions. 3. The method of claim 1, wherein generating the links is further based at least in part on a number of transitions pertaining to the links for the travel between the two or more regions. 4. The method of claim 3, wherein the number of transitions is associated with a departure time from at least a region of origin and an arrival time in at least a region of destination, the region of origin and the region of destination comprising at least two of the two or more regions of the area. 5. The method of claim 1, further comprising: calculating scores of minimum distort of features for each of the links in a particular time frame of the plurality of time frames; andidentifying extreme values among the scores of minimum distort as at least some of the outliers. 6. The method of claim 5, wherein the calculating the scores of minimum distort includes computing an Euclidean distance to calculate a difference between each feature of two time frames of the plurality of time frames, wherein the two time frames pertain to a same link. 7. The method of claim 1, wherein a time frame of the plurality of time frames is determined based at least in part on: separating the GPS points into weekdays and at least one of weekends or holidays of a year; andassigning the GPS points to time bins representative of thirty minute increments of a day. 8. The method of claim 1, further comprising: creating a three-dimensional unit cube for individual time frames of the plurality of time frames, the three-dimensional unit cube including a feature vector comprising:a total number of service vehicles on a link between an origin region and a destination region of the regions associated with the area;a proportion of the service vehicles among the total number of the service vehicles moving out of the origin region during a particular time frame; anda proportion of the service vehicles among the total number of the service vehicles moving into the destination region in the particular time frame and identifying extreme points farthest away from a center data cluster as at least some of the outliers in the particular time frame. 9. The method of claim 1, further comprising: constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from a first time frame of the plurality of time frames through a last time frame of the plurality of time frames;determining that a first outlier of the outliers occurred at a time before a second outlier of the outliers;determining that the first outlier and the second outlier are spatially correlated;determining that the first outlier is a parent of the second outlier; and adding the parent and a child that is dependent on the parent in the outlier trees. 10. The method of claim 1, further comprising determining spatiotemporal causal relationships from outlier trees by: constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from a first time frame of the plurality of time frames through a last time frame of the plurality of time frames; anddiscovering frequent subtrees from the constructed outlier trees that correspond to a causality and a relationship among the frequent subtrees to represent abnormal traffic patterns in the GPS points. 11. The method of claim 10, further comprising providing the recommendations based at least in part on the frequent subtrees including abnormal traffic patterns, the recommendations including diverting traffic to less travelled roads, building additional roads, suggesting a bus route, or suggesting a subway line. 12. The computer storage media of claim 1, wherein the calculating the scores of minimum distort includes computing an Euclidean distance to calculate a difference between each feature of two time frames pertaining to a same link. 13. One or more computer storage media encoded with instructions that, when executed by a processor, perform acts comprising: accessing, from a database associated with a content service provider, logs of global positioning system (GPS) points collected by geolocation sensors associated with service vehicles;identifying geographical locations from the GPS points to represent an area where the service vehicles travelled as recorded in the logs;generating links to connect two or more regions of the area based at least in part on a number of transitions pertaining to the links for travel of the service vehicles between the two or more regions; anddetecting outliers in the GPS points in the geographical locations based at least in part on the links. 14. The computer storage media of claim 13, wherein: at least some of the GPS points correspond to similar time spans in a year; andthe outliers are detected based at least in part on GPS points that correspond to the similar time spans in the year. 15. The computer storage media of claim 13, wherein the number of transitions is associated with a departure time from at least a region of origin and an arrival time in at least a region of destination, the region of origin and the region of destination comprising at least two of the two or more regions. 16. The computer storage media of claim 13, wherein the acts further comprise: calculating scores of minimum distort of features for each of the links in a time frame; andidentifying extreme values among the scores of minimum distort as at least some of the outliers. 17. A device comprising: one or more processors;computer storage media; andone or more modules maintained in the computer storage media and executable on the one or more processors to perform one or more operations comprising:accessing, from a database associated with a content service provider, logs of global positioning system (GPS) points collected by geolocation sensors associated with service vehicles; identifying geographical locations from the GPS points to represent an area where the service vehicles travelled as recorded in the logs;dividing the area into a plurality of regions based at least in part on major roads;generating links between pairs of regions of the plurality of regions based at least in part on travel by the service vehicles between the plurality of regions of the area in a plurality of time frames; anddetecting outliers in the GPS points in the geographical locations based at least in part on the links. 18. The device of claim 17, operations further comprising: constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from a first time frame of the plurality of time frames through a last time frame of the plurality of time frames;determining that a first outlier of the outliers occurred at a time before a second outlier of the outliers, the first outlier and the second outlier being spatially correlated;determining that the first outlier detected is a parent of the second outlier; andadding the parent and a child that is dependent on the parent in the outlier trees being constructed. 19. The device of claim 17, operations further comprising: constructing outlier trees based on temporal and spatial properties of the outliers being detected by determining dependencies of the outliers from a first time frame of the plurality of time frames through a last time frame of the plurality of time frames; anddiscovering frequent subtrees from the constructed outlier trees that correspond to a causality and a relationship among the frequent subtrees to represent abnormal traffic patterns in the GPS points. 20. The device of claim 19, operations further comprising providing, via a user interface associated with the device, recommendations based at least in part on the frequent subtrees including abnormal traffic patterns, the recommendations including diverting traffic to less travelled roads, building additional roads, suggesting a bus route, or suggesting a subway line.
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는 부적절한 답변을 할 수 있습니다.