Amin Vahedian Khezerlou
Zhou, X., Khezerlou, A. V., Liu, A., Shafiq, Z., & Zhang, F. (2016, October). A traffic flow approach to early detection of gathering events. In Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (p. 4). ACM.
Abstract: Given a spatial field and the traffic flow between neighboring locations, the early detection of gathering events (edge) problem aims to discover and localize a set of most likely gathering events. It is important for city planners to identify emerging gathering events which might cause public safety or sustainability concerns. However, it is challenging to solve the edge problem due to numerous candidate gathering footprints in a spatial field and the non-trivial task to balance pattern quality and computational efficiency. Prior solutions to model the edge problem lack the ability to describe the dynamic flow of traffic and the potential gathering destinations because they rely on static or undirected footprints. In contrast, in this paper, we model the footprint of a gathering event as a Gathering directed acyclic Graph (G-Graph), where the root of the G-Graph is the potential destination and the directed edges represent the most likely paths traffic takes to move towards the destination. We also proposed an efficient algorithm called SmartEdge to discover the most likely non-overlapping G-Graphs in the given spatial field. Our analysis shows that the proposed G-Graph model and the SmartEdge algorithm have the ability to efficiently and effectively capture important gathering events from real-world human mobility data. Our experimental evaluations show that SmartEdge saves 50% computation time over the baseline algorithm.
Khezerlou, A. V., Zhou, X., Li, L., Shafiq, Z., Liu, A. X., & Zhang, F. (2017). A traffic flow approach to early detection of gathering events: Comprehensive results. ACM Transactions on Intelligent Systems and Technology (TIST), 8(6), 74.
Abstract: Given a spatial field and the traffic flow between neighboring locations, the early detection of gathering events (EDGE) problem aims to discover and localize a set of most likely gathering events. It is important for city planners to identify emerging gathering events thatmight cause public safety or sustainability concerns. However, it is challenging to solve the EDGE problem due to numerous candidate gathering footprints in a spatial field and the nontrivial task of balancing pattern quality and computational efficiency. Prior solutions to model the EDGE problem lack the ability to describe the dynamic flow of traffic and the potential gathering destinations because they rely on static or undirected footprints. In our recent work, wemodeled the footprint of a gathering event as a Gathering Graph (G-Graph), where the root of the directed acyclic G-Graph is the potential destination and the directed edges represent the most likely paths traffic takes to move toward the destination. We also proposed an efficient algorithm called SmartEdge to discover the most likely nonoverlapping G-Graphs in the given spatial field. However, it is challenging to perform a systematic performance study of the proposed algorithm, due to unavailability of the ground truth of gathering events. In this article, we introduce an event simulation mechanism, which makes it possible to conduct a comprehensive performance study of the SmartEdge algorithm. We measure the quality of the detected patterns, in a systematic way, in terms of timeliness and location accuracy. The results show that, on average, the SmartEdge algorithm is able to detect patterns within a grid cell away (less than 500 meters) of the simulated events and detect patterns of the simulated events as early as 10 minutes prior to the first arrival to the gathering event.
Vahedian, A., Zhou, X., Tong, L., Li, Y., & Luo, J. (2017, November). Forecasting gathering events through continuous destination prediction on big trajectory data. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (p. 34). ACM.
Abstract: Urban gathering events such as social protests, sport games, and traffic congestions bring significant challenges to urban management. Identifying gathering events timely is thus an important problem for city administrators and stakeholders. Previous techniques on gathering event detection are mostly descriptive, i.e., using real-time on-site observations (e.g., taxi drop-offs, traffic volume) to detect the gathering events that have already emerged. In this paper we propose a predictive approach to identify future gathering events through destination prediction of incomplete trajectories. Our approach consists of two parts, i.e., destination prediction and event forecasting. For destination prediction, we relax the Markov property assumed in most of the related work and address the consequent high-memory-cost challenge by proposing a novel Via Location Grouping (VIGO) approach for destination prediction. For event forecasting, we design an online prediction mechanism that learns from both historical and recent trajectories to address the non-stationarity of urban trip patterns. Gathering events are forecast based on projected arrivals in each location and time. A case study on real taxi data in Shenzhen, China shows that our proposed approach can correctly and timely predict gathering events. Extensive experiments show that the proposed VIGO approach achieves higher accuracy than related work for destination prediction and saves more than 82% memory cost over a baseline approach. The event forecasting based on VIGO is effective and fast enough for continuous event forecasting at one-minute frequency.
Zhou, Xun and Rong, Huigui and Yang, Chang and Khezerlou, Amin Vahedian and Zheng, Hui and Shafiq, Zubair and Liu, Alex X (2018). Optimizing Taxi Driver Profit Efficiency: A Spatial Network-based Markov Decision Process Approach. IEEE Transactions on Big Data, DOI: 10.1109/TBDATA.2018.2875524.
Abstract: Taxi services play an important role in the public transportation system of large cities. Improving taxi business efficiency is an important societal problem. Most of the recent analytical approaches on this topic only considered how to maximize the pickup chance, energy efficiency, or profit for the immediate next trip when recommending seeking routes, therefore may not b optimal for the overall profit over an extended period of time due to ignoring the destination choice of potential passengers. To tackle this issue, we propose a novel Spatial Network-based Markov Decision Process (SN-MDP) with a rolling horizon configuration to recommend better driving directions. Given a set of historical taxi records and the current status (e.g., road segment and time) of a vacant taxi, we find the best move for this taxi to maximize the profit in the near future. We propose statistical models to estimate the necessary time-variant parameters of SN-MDP from data to avoid competition between drivers. In addition, we take into account fuel cost to assess profit, rather than only income. A case study and several experimental evaluations on a real taxi dataset show that our proposed approach improves the profit efficiency by up to 13.7%.
Xiong, Haoyi and Vahedian, Amin and Zhou, Xun and Li, Yanhua and Luo, Jun (2018). Predicting Traffic Congestion Propagation Patterns: A Propagation Graph Approach. 11th ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS’18).
Abstract: A traffic congestion in a road network may propagate to upstream road segments. Such a congestion propagation may make a series of connected road segments congested in the near future. Given a spatial-temporal network and congested road segments in current time, the aim of predicting traffic congestion propagation pattern is to predict where those congestion will propagate to. This can provide users (e.g. city officials) with valuable information on how congestion will propagate in the near future to help mitigating emerging congestions. However, it is challenging to predict in real-time due to complex propagation process between roads and high computational intensity caused by large dataset. Recent studies have been focusing on finding frequent or most likely congestion propagation patterns in historical data. In contrast, this research will address the problem of predicting congestion propagation patterns in the near future. We predict the footprint of congestion propagation as Propagation Graphs (Pro-Graphs) where the root of each Pro-Graph is a set of congested roads propagating congestion to nearby roads. We propose an efficient algorithm called PPI_Fast to achieve this prediction. Our experiments on real-word dataset from Shenzhen, China shows that the PPI_Fast is able to predict near future propagations with AUC of 0.75 and improves the running time of the baseline algorithm. Two case studies have been done to show our work can find meaningful patterns.
Chiu, J, Vahedian, A. Zhou, X. (2018). Understanding Business Location Choice Pattern: A Co-Location Analysis on Urban POI Data. INFORMS Workshop on Data Science. Phoenix, AZ 2018.
Abstract: The co-localization of businesses has concerned researchers for a long time. With the advances in technology, for the first time we have access to accurate and up-to-date location information of businesses in form of public digital maps. This creates an opportunity to analyze the co-location patterns of the businesses with a data-driven approach to obtain an objective and realistic view of such patterns. In this study, we analyze the clustering tendencies and the co-location patterns of the businesses in the three largest cities of the United States. We obtain the dataset using the Google Maps Places API. We first obtain top co-locating patterns using co-location pattern mining techniques. Then we test the significance of the patterns using statistical tests and Monte-Carlo simulation. We find interesting co-location and clustering tendencies among brand names within and across industries as well as clustering tendencies between businesses of certain industries.
Vahedian, A., Zhou, X., Tong, L., Li, Y., & Luo, J. (revised in 2018). Forecasting Gathering Events through Trajectory Destination Prediction: A Dynamic Hybrid Model. IEEE Transactions on Knowledge and Data Engineering (TKDE) – (Under review after revision).
Abstract: Identifying urban gathering events is an important problem due to challenges it brings to urban management. Recently, we proposed a hybrid model (H-VIGO-GIS) to predict future gathering events through trajectory destination prediction. Our approach consisted of two models: historical and recent and continuously predicted future gathering events. However, H-VIGO-GIS has limitations. (1) The recent model does not capture the newly-emerged abnormal patterns effectively, since it uses all recent trajectories, including normal ones. (2) The recent model is sparse due to limited number of trajectories it learns, i.e. it cannot produce predictions in many cases, forcing us to rely only on the historical model. (3) The accuracy of both recent and historical models varies by space and time. Therefore, combining them the same way at all times and places undermines the overall accuracy of the hybrid model. Addressing these issues, in this paper we propose a Dynamic Hybrid model called (DH-VIGO-TKDE) that addresses the above-mentioned issues. We perform comprehensive evaluations using real-world data and an event simulator. The experiments show the proposed model significantly improves the prediction accuracy and timeliness of forecasting gathering events, resulting in precision of 0.85 and recall of 0.67 as opposed to 0.5 and 0.3 of H-VIGO-GIS.