Modern cities generate vast streams of urban dynamics data reflecting mobility demand, environmental conditions, and traffic patterns. The value of these data lies not only in individual modalities but in their integration—urban signals are highly interdependent, with changes in one modality often influencing others. Consequently, predicting any single urban dynamic requires information from multiple interrelated sources. Although numerous methods—ranging from deep learning models to recent LLM-based approaches—have been proposed, most are limited in scope. They either focus on single-modality prediction, rely on rigid model designs that lack flexibility, or overlook inter-modal dependencies. As a result, they struggle to adapt to dynamic urban conditions and suffer from degraded predictive performance across modalities. In this paper, we propose UniLLM, a unified large language model for multi-modal urban dynamics prediction. At its core, UniLLM introduces a Unified Cross-Modal Alignment Module that transforms heterogeneous urban data into latent representations while preserving modality-specific patterns and capturing cross-modal correlations through a contrastive learning objective. To support dynamic adaptation across tasks and modalities, we design a Routing-Aware Prompting Mechanism that learns soft prompts based on task context and modality semantics. Furthermore, a Multi-Modal Memory-Guided Adaptive Algorithm employs replay-based gradient coordination and Frank–Wolfe optimization to mitigate cross-modal catastrophic forgetting during fine-tuning. Extensive experiments across multiple cities and urban modalities demonstrate that UniLLM consistently outperforms state-of-the-art baselines. These results highlight UniLLM's potential as a flexible and robust forecasting model for real-world, multi-modal urban environments.

This paper introduces a novel approach to fine-tuning transformer-based models for various spatial-temporal downstream tasks. While fine-tuning approaches have shown remarkable success in fields like natural language processing, their efficacy in human-generated spatial-temporal data is often hindered by the complex spatial-temporal correlation and extensive reliance on labeled data. We introduce Knowledge Graph-Guided Spatial-Temporal Cross-task Fine-Tuning method, i.e., KG-STFT, a cross-task fine-tuning approach designed for adapting to data-scarce spatial-temporal tasks by leveraging rich knowledge embedded in similar downstream tasks and pre-trained model. Our KG-STFT framework utilizes i) a non-linear knowledge ensembler to capture and integrate knowledge embedded in different transformer blocks, and ii) constructs a task knowledge graph to "transfer" knowledge from data-rich to data-scarce tasks. Empirical experiments on real-world taxi trajectory data show that KG-STFT outperforms baselines, especially in data-scarce tasks, by leveraging task commonalities to improve fine-tuning.

The problem of human spatiotemporal (ST) decision understanding, which consists of extracting faithful and interpretable decision strategies from human agents' behavioral records in space and time, is important for many applications, such as improving taxi drivers' route planning and efficiency. It is challenging because ST data are not as readily interpretable as images or text data, which leads to difficulties in constructing data-driven explanations. Existing research on this topic defines the problem as a Markov Decision Process (MDP) and uses imitation learning to extract a policy approximating the underlying human policy for post-hoc interpretation. However, such methods cannot provide direct interpretation through model training and may result in incomprehensible interpretations when using ST data. We address these limitations by designing ConPro-GAIL, a prototype-based interpretable GAIL model for intrinsically interpretable ST policy extraction. ConPro-GAIL learns and represents the optimal policy in terms of prototypical sets of concepts that correspond to general scenarios in the MDP. It explains a decision associated with an input state via inductive generalization from what occurred in the state's most similar prototypes to the input state itself. Experiments and case studies on two taxi trajectory datasets show that ConPro-GAIL achieves better policy faithfulness than its black-box competitors and better interpretability than post-hoc explainers.

The development of sensing technologies has broad-ened the scope of urban dynamics research. However, existing methods primarily focus on using isolated aspects of urban data, limiting their ability to capture the complex spatial-temporal dependency among different urban dynamics and generalizability across applications. Addressing these shortcomings requires a more comprehensive model capable of integrating multifaceted data, generating generalized representations adaptable to diverse applications and scenarios. In this paper, we introduce the Multifaceted SpAtial-TempoRal ContrastivE Learning framework, i.e., MARCEL, an innovative approach designed to learn robust, universally applicable, and adaptable representations of multifaceted urban dynamics through contrastive learning. MARCEL employs pretrained preliminary representation learning modules to extract distinct spatial-temporal dependencies inherent to each urban dynamic independently. It then features a Spatial-Temporal Contrastive Learning strategy to capture unified spatial-temporal patterns, including asynchronous, conflicting, and complementary behaviors across multifaceted urban dynamics. Additionally, MARCEL integrates a Multifaceted Knowledge Transfer mechanism to capture inter-dependencies among different urban dynamics and facilitate knowledge sharing. The learned representations are highly generalizable and can be applied effectively to various downstream tasks. Extensive experiments on real-world urban datasets demonstrate that MARCEL is effective and significantly outperforms state-of-the-art baselines.

Understanding and predicting urban dynamics is crucial for managing transportation systems, optimizing urban planning, and enhancing public services. While neural network-based approaches have achieved success, they often rely on task-specific architectures and large volumes of data, limiting their ability to generalize across diverse urban scenarios. Meanwhile, Large Language Models (LLMs) offer strong reasoning and generalization capabilities, yet their application to spatial-temporal urban dynamics remains underexplored. Existing LLM-based methods struggle to effectively integrate multifaceted spatial-temporal data and fail to address distributional shifts between training and testing data, limiting their predictive reliability in real-world applications. To bridge this gap, we propose UrbanMind, a novel spatial-temporal LLM framework for multifaceted urban dynamics prediction that ensures both accurate forecasting and robust generalization. At its core, UrbanMind introduces Muffin-MAE, a multifaceted fusion masked autoencoder with specialized masking strategies that capture intricate spatial-temporal dependencies and intercorrelations among multifaceted urban dynamics. Additionally, we design a semantic-aware prompting and fine-tuning strategy that encodes spatial-temporal contextual details into prompts, enhancing LLMs' ability to reason over spatial-temporal patterns. To further improve generalization, we introduce a test time adaptation mechanism with a test data reconstructor, enabling UrbanMind to dynamically adjust to unseen test data by reconstructing LLM-generated embeddings. Extensive experiments on real-world urban dynamics datasets from multiple cities demonstrate the effectiveness of UrbanMind. The results consistently show that UrbanMind outperforms state-of-the-art baselines, achieving superior accuracy and strong generalization, even in zero-shot scenarios with no prior data.

Given historical traffic distributions and associated urban conditions observed in a city, the conditional urban traffic estimation problem aims at estimating realistic future projections of the traffic under a set of new urban conditions, e.g., new bus routes, rainfall intensity, and travel demands. The problem is important in reducing traffic congestion, improving public transportation efficiency, and facilitating urban planning. However, solving this problem is challenging due to the strong spatial dependencies of traffic patterns and the complex relations between the traffic and urban conditions. Recently, we proposed a Complex-Condition-Controlled Generative Adversarial Network ( \(\boldsymbol{C^{3}}\) -GAN) , which tackles both of the challenges and solves the urban traffic estimation problem under various complex conditions by adding a fixed embedding network and an inference network on top of the standard conditional GAN model. The randomly chosen embedding network transforms the complex conditions to latent vectors, and the inference network enhances the connections between the embedded vectors and the traffic data. However, a randomly chosen embedding network cannot always successfully extract features of complex urban conditions, which indicates \(C^{3}\) -GAN is unable to uniquely map different urban conditions to proper latent distributions. Thus, \(C^{3}\) -GAN would fail in certain traffic estimation tasks. Besides, \(C^{3}\) -GAN is hard to train due to vanishing gradients and mode collapse problems. To address these issues, in this article, we extend our prior work by introducing a new deep generative model, namely, \(C^{3}\) -GAN \(+\) , which significantly improves the estimation performance and model stability. \(C^{3}\) -GAN \(+\) has new objective, architecture, and training algorithm. The new objective applies Wasserstein loss to the conditional generation case to encourage stable training. Shared convolutional layers between the discriminator and the inference network help to capture spatial dependencies of traffic more efficiently, part of the shared convolutional layers are used to update the embedding network periodically aiming to encourage good representation and avoid model divergence. Extensive experiments on real-world datasets demonstrate that our \(C^{3}\) -GAN \(+\) produces high-quality traffic estimations and outperforms state-of-the-art baseline methods.

Traffic accident forecasting is an important task for intelligent transportation management and emergency response systems. However, this problem is challenging due to the spatial heterogeneity of the environment. Existing data-driven methods mostly focus on studying homogeneous areas with limited size (e.g. a single urban area such as New York City) and fail to handle the heterogeneous accident patterns over space at different scales. Recent advances (e.g. spatial ensemble) utilize pre-defined space partitions and learn multiple models to improve prediction accuracy. However, external knowledge is required to define proper space partitions before training models and predefined partitions may not necessarily reduce the heterogeneity. To address this issue, we propose a novel Learning-Integrated Space Partition Framework (LISA) to simultaneously learn partitions while training models, where the partitioning process and learning process are integrated in a way that partitioning is guided explicitly by prediction accuracy rather than other factors. Experiments using real-world datasets, demonstrate that our work can capture underlying heterogeneous patterns in a self-guided way and substantially improve baseline networks by an average of 13.0%.

The problem of traffic dynamics prediction, aiming to capture the complicated patterns of urban dynamics and forecast short-term future traffic status, is essential for managing transportation systems, reducing congestion, enhancing safety, improving commuter efficiency, and supporting urban planning and infrastructure development. Current approaches using ma-chine learning and deep neural networks have advanced traffic prediction but often focus on individual urban dynamic aspects and rely on auto-regressive methods for consecutive predictions, which can be inaccurate and computationally expensive. In this work, we propose the Spatial- Temporal Graph LAtent DIffusion ModeL (STGAIL) to address these limitations. STGAIL views geographical regions as graphs with various traffic features, capturing their interconnections. Operating in a pre-trained latent space, STGAIL uses latent diffusion processes and inno-vative spatial-temporal graph layers for accurate and efficient multi-step predictions. Fine-tuning with temporal binary masks further enhances its performance, avoiding error accumulation and reducing computational costs. Experiments on real-world datasets demonstrate STGAIL's superior accuracy and efficiency over state-of-the-art methods. We also make our code and dataset available, contributing to ongoing research in traffic dynamics prediction.

Enhancing diverse human decision-making processes in an urban environment is a critical issue across various applications, including ride-sharing vehicle dispatching, public transportation management, and autonomous driving. Offline reinforcement learning (RL) is a promising approach to learn and optimize human urban strategies (or policies) from pre-collected human-generated spatial-temporal urban data. However, standard offline RL faces two significant challenges: (1) data scarcity and data heterogeneity, and (2) distributional shift. In this paper, we introduce MODA - a Multi-Task Offline Reinforcement Learning with Contrastive Data Sharing approach. MODA addresses the challenges of data scarcity and heterogeneity in a multi-task urban setting through Contrastive Data Sharing among tasks. This technique involves extracting latent representations of human behaviors by contrasting positive and negative data pairs. It then shares data presenting similar representations with the target task, facilitating data augmentation for each task. Moreover, MODA develops a novel model-based multi-task offline RL algorithm. This algorithm constructs a robust Markov Decision Process (MDP) by integrating a dynamics model with a Generative Adversarial Network (GAN). Once the robust MDP is established, any online RL or planning algorithm can be applied. Extensive experiments conducted in a real-world multi-task urban setting validate the effectiveness of MODA. The results demonstrate that MODA exhibits significant improvements compared to state-of-the-art baselines, showcasing its capability in advancing urban decision-making processes. We also made our code available to the research community.

Human-generated Spatial-Temporal Data (HSTD), represented as trajectory sequences, has undergone a data revolution, thanks to advances in mobile sensing, data mining, and AI. Previous studies have revealed the effectiveness of employing attention mechanisms to analyze massive HSTD. However, traditional attention models face challenges when managing lengthy and noisy trajectories as their computation comes with large memory overheads. Furthermore, attention scores within HSTD trajectories are sparse (i.e., most of the scores are zeros), and clustered with varying lengths (i.e., consecutive tokens clustered with similar scores). To address these challenges, we introduce an innovative strategy named Memory-efficient Trajectory Attention (MeTA). We leverage complicated spatial-temporal features (e.g., traffic speed, proximity to PoIs) and design an innovative feature-based trajectory partition technique to shrink trajectory length. Additionally, we present a learnable dynamic sorting mechanism, with which attention is only computed between sub-trajectories that have prominent correlations. Empirical validations using real-world HSTD demonstrate that our approach not only yields competitive results but also significantly lowers memory usage compared with state-of-the-art methods. Our approach presents innovative solutions for memory-efficient trajectory attention, offering valuable insights for handling HSTD efficiently.

Rapid advances in perception, planning, and decision-making areas for self-driving vehicles have led to great improvements in their function and capabilities and enabled several prototypes to be driving on the roads and streets, such as Waymo Driver, TuSimple, Nuro, etc. Among various applications of self-driving vehicles, a promising one is the ride service as it has the potential to improve service quality and productivity and to provide service to anyone at any time. Extensive studies have been conducted on self-driving planning and safety, but few works focus on self-driving ride service decision-making and routing. In this work, we take the lead to study self-driving ride service planning and decision-making problem leveraging human-generated spatial-temporal data, and propose the data-driven Conservative Actor-Critic approach – CAC – based on offline reinforcement learning. Our CAC is able to make conservative decisions in a complicated environment with multiple goal states, and avoid dangerous and overly optimistic behaviors by exploiting human decisions. Extensive experiments with real-world data demonstrate that our CAC-learned policies are able to improve taxi service operation efficiency and quality drastically in terms of shortening passenger waiting time and improving service revenue.

Advancements in mobile sensing, data mining, and artificial intelligence have revolutionized the collection and analysis of Human-generated Spatial-Temporal Data (HSTD), paving the way for diverse applications across multiple domains. However, previous works have primarily focused on designing task-specific models for different problems, which lack transferability and generalizability when confronted with diverse HSTD. Additionally, these models often require a large amount of labeled data for optimal performance. While pre-trained models in Natural Language Processing (NLP) and Computer Vision (CV) domains have showcased impressive transferability and generalizability, similar efforts in the spatial-temporal data domain have been limited. In this paper, we take the lead and introduce the Spatial-Temporal Pre-Training model, $i.e$., STPT, which is connected with a self-supervised learning task, to address these limitations. STPT enables the creation of robust and versatile representations of HSTD. We validate our framework using real-world data and demonstrate its efficacy through two downstream tasks, $i.e$., trajectory classification and driving activity identification $(e.g$., identifying seeking $vs$. serving behaviors in taxi trajectories). Our results achieve an accuracy of 83.125% (16.2% higher than the average baseline) for human mobility identification and an accuracy of 77.88% (13.0% higher than the average baseline) for the human activity identification task. These outcomes underscore the potential of our pre-trained model for diverse downstream applications within the spatial-temporal data domain.

The Human Mobility Signature Identification (HuMID) problem aims at determining whether the incoming trajectories were generated by a claimed agent from the historical movement trajectories of a set of individual human agents such as pedestrians and taxi drivers. The HuMID problem is significant, and its solutions have a wide range of real-world applications, such as criminal identification for police departments, risk assessment for auto insurance providers, driver verification in ride-sharing services, and so on. Though Deep neural networks (DNN) based HuMID models on spatial-temporal mobility fingerprint similarity demonstrate remarkable performance in effectively identifying human agents' mobility signatures, it is vulnerable to adversarial attacks as other DNN-based models. Therefore, in this paper, we propose a Spatial-Temporal iterative Fast Gradient Sign Method with L0 regularization - ST-iFGSM - to detect the vulnerability and enhance the robustness of HuMID models. Extensive experiments with real-world taxi trajectory data demonstrate the efficiency and effectiveness of our ST-iFGSM algorithm. We tested our method on both the ST-SiameseNet and an LSTM-based HuMID classification model. It shows that ST-iFGSM can generate successful attacks to fool the HuMID models with only a few steps of attack in a small portion of the trajectories. The generated attacks can be used as augmented data to update and improve the HuMID model accuracy significantly from 47.36% to 76.18% on testing samples after the attack(86.25% on the original testing samples).

With large amounts of human-generated spatial-temporal urban data (e.g., GPS trajectories of vehicles, passengers’ trip data on buses and trains, etc.), human urban strategy analysis has become an important problem in many urban scenarios. This problem is hard to solve due to two major challenges: (1) data scarcity (i.e., each human agent can only provide limited observations) and (2) data heterogeneity (i.e., having mixed observations from many different human agents). Most of the existing works on this problem usually require a large amount of historical observations aiming to correctly infer a human agent's urban strategy and thus fail to properly address both challenges at the same time. To solve the human urban strategy analysis problem in case of data scarcity and data heterogeneity, we design a novel learning paradigm — Spatial-Temporal Meta-GAIL (STM-GAIL), which can successfully learn diverse human urban strategies from heterogeneous human-generated spatial-temporal urban data. STM-GAIL models the human decision processes as variable length Markov decision processes (VLMDPs) and incorporates the surrounding spatial feature patterns (e.g., traffic volume patterns, etc.) into states to better capture the spatial-temporal dependencies of human decisions. Besides, STM-GAIL learns diverse human urban strategies from the meta-learning perspective, and can distinguish various human urban strategies by adding an inference network on top of the standard GAIL. STM- GAIL can be quickly adapted to a new human expert's urban strategy with a single trajectory. Extensive experiments on real-world human-generated spatial-temporal dataset are performed.

The conditional urban traffic estimation problem aims to accurately estimate the future traffic status based on the changing local travel demands, which has long been an important issue in urban planning. However, most existing methods require the target city to provide a large amount of traffic data. Once traffic estimation is performed in a “new” city where many urban services and transportation infrastructures are not built and thus no prior data is available, those works would fail due to the lack of data. In this paper, we aim to solve the conditional urban traffic estimation problem in case of data scarcity (i.e., the target city cannot provide any prior data) and tackle the main challenges including (1) knowledge learning from the source and (2) knowledge adaptation without prior traffic data. We propose a novel generative adversarial network — Meta Spatial-Temporal Generative Adversarial Network (Mest-GAN), which can successfully estimate traffic in the target city based on local travel demands without the access to any prior traffic data. To address the first challenge, we learn the latent distribution of travel demands with the inference network, the latent distribution also indicates the diverse spatial-temporal traffic patterns. To solve the second challenge, we use the travel demand data in the target city for adaptation, where the inference network infers a latent code guiding the generator to produce accurate traffic estimations. Extensive experiments on real-world multiple-city datasets demonstrate that our Mest-GAN produces high-quality traffic estimations and outperforms state-of-the-art baseline methods.

Conditional traffic estimation is a vital problem in urban plan deployment, which can help evaluate urban construction plans and improve transportation efficiency. Conventional methods for conditional traffic estimation usually focus on supervised settings, which require a large amount of labeled training data. However, in many urban planning applications, the large amount of traffic data in a new city can be hard or impossible to acquire. To tackle the conditional traffic estimation problem in data scarcity situations, we formulate the problem as a spatial transfer generative learning problem. Compared to prior spatial transfer learning frameworks with only single source city, we propose to extracts knowledge from multiple source cities to improve the estimation accuracy and transfer stability, which is a technically more challenging task. As a solution, we propose a new cross-city conditional traffic estimation method — Spatially-Transferable Generative Adversarial Networks (STrans-GAN) with novel pre-training and fine-tuning algorithms. STransGAN preserves diverse traffic patterns from multiple source cities through traffic clustering, and incorporates meta-learning idea into the pre-training process to learn a well-generalized model. During fine-tuning, we propose to add a cluster matching regularizer to realize the flexible adaptation in different scenarios. Through extensive experiments on multiple-city datasets, the effectiveness of STrans-GAN is proved.

Urban traffic status (e.g., traffic speed and volume) is highly dynamic in nature, namely, varying across space and evolving over time. Thus, predicting such traffic dynamics is of great importance to urban development and transportation management. However, it is very challenging to solve this problem due to spatial-temporal dependencies and traffic uncertainties. In this article, we solve the traffic dynamics prediction problem from Bayesian meta-learning perspective and propose a novel continuous spatial-temporal meta-learner (cST-ML), which is trained on a distribution of traffic prediction tasks segmented by historical traffic data with the goal of learning a strategy that can be quickly adapted to related but unseen traffic prediction tasks. cST-ML tackles the traffic dynamics prediction challenges by advancing the Bayesian black-box meta-learning framework through the following new points: (1) cST-ML captures the dynamics of traffic prediction tasks using variational inference, and to better capture the temporal uncertainties within tasks, cST-ML performs as a rolling window within each task; (2) cST-ML has novel designs in architecture, where CNN and LSTM are embedded to capture the spatial-temporal dependencies between traffic status and traffic-related features; (3) novel training and testing algorithms for cST-ML are designed. We also conduct experiments on two real-world traffic datasets (taxi inflow and traffic speed) to evaluate our proposed cST-ML. The experimental results verify that cST-ML can significantly improve the urban traffic prediction performance and outperform all baseline models especially when obvious traffic dynamics and temporal uncertainties are presented.

Thanks to the rapid development of mobile sensing techniques, massive human-generated spatial-temporal data (HSTD) are generated from the urban areas, e.g., passenger-seeking trajectories from taxi drivers, and public transit trips from urban dwellers. These HSTD record sequential decisions made by human agents. Studying human behavior from HSTD provides benefits to many aspects, for example, studying passenger-seeking strategies from experienced taxi drivers can help improve the operation efficiencies of those new drivers. One common method to analyze human behavior from HSTD is Imitation Learning (IL). Existing IL approaches rely on data collected from experts. However, human agents who generate HSTD may have diverse expertise levels across geographical regions, i.e., with good policies in some regions and poor policies in less experienced regions. The problem of how to infer the optimal policy for agents in their unfamiliar or less-experienced regions remains open. In this paper, we propose the novel Generative Adversarial Imitation Learning for Non-experts (NEXT-GAIL) framework to first disentangle expert knowledge, which is irrelevant to spatial-temporal regions, from the demonstration data. Then, such knowledge can be transferred to regions, where the agent does not possess an expert policy. We take the real-world taxi trajectory data as an example to evaluate the performance of our proposed framework. The comparison results illustrate that our proposed NEXT-GAIL outperforms existing state-of-the-art approaches regarding the accuracy of the inferred optimal policy for non-experts.

k nearest neighbor (kNN) queries and skyline queries are important operators on multi-dimensional data points. Given a query point, kNN returns the k nearest neighbors based on a scoring function such as a weighted sum of the attributes, which requires predefined attribute weights (or preferences). Skyline returns all possible nearest neighbors for any monotonic scoring functions without requiring attribute weights but the number of returned points can be prohibitively large.In this paper, we propose an eclipse operator that generalizes the classic 1NN and skyline queries and provides a more customizable query solution for users. In eclipse, users can specify rough and customizable attribute preferences and control the number of returned points. We show that both 1NN and skyline are instantiations of eclipse. To process eclipse queries, we propose a baseline algorithm with time complexity O(n22d-1), and an improved O(nlogd-1n) time transformationbased algorithm, where n is the number of points and d is the number of dimensions. Furthermore, we propose a novel index-based algorithm utilizing duality transform with much better efficiency. The experimental results on the real NBA dataset and the synthetic datasets demonstrate the effectiveness of the eclipse operator and the efficiency of our eclipse algorithms.

Given historical traffic distributions and associated urban conditions observed in a city, the conditional urban traffic estimation problem aims at estimating realistic future projections of the traffic under a set of new urban conditions, e.g., new bus routes, rainfall intensity and travel demands. The problem is important in reducing traffic congestion, improving public transportation efficiency, and facilitating urban planning. However, solving this problem is challenging due to the strong spatial dependencies of traffic patterns and the complex relations between the traffic and urban conditions. In this paper, we tackle the challenges by proposing a novel Complex-Condition-Controlled Urban Traffic Estimation through Generative Adversarial Networks (C3-GAN) for urban traffic estimation of a region under various complex conditions. C3-GAN features the following three novel designs on top of standard cGAN model: (1) an embedding network mapping the complex conditions to a latent space to find representations of the urban conditions; (2) an inference network to enhance the relations between the embedded latent vectors and the traffic data. Extensive experiments on real-world datasets demonstrate that our C3-GAN produces high-quality traffic estimations and outperforms state-of-the-art baseline methods.

Given the underlying road network of an urban area, the problem of urban dynamics prediction aims to capture the patterns of urban dynamics and to forecast short-term urban traffic status continuously from the historical observations. This problem is of fundamental importance to urban traffic management, planning, and various business services. However, predicting urban dynamics is challenging due to the highly dynamic (i.e., varying across geographical locations and evolving over time) and uncertain (i.e., affected by unexpected factors) nature of urban traffic systems. Recent works adopt meta-learning approaches to capture irregular and rare patterns but make unrealistic assumptions such as single-domain uncertainties and explicit temporal task segmentation. In this paper, we solve the urban dynamics prediction problem from the Bayesian meta-learning perspective and propose a novel domain adaptable continuous meta-learning approach (DAC-ML) that does not require task segmentation. Trained on a sequence of spatial-temporal urban dynamics data, DAC-ML aims to detect and infer unobserved latent variations (from task and domain levels) and generalize well in a sequential prediction setting, where the underlying data generating process varies over time. Experimental results on three real-world datasets demonstrate that DAC-ML can outperform baselines in urban dynamics prediction, especially when obvious urban dynamics and temporal uncertainties are present.

Given a set of user-specified locations and a massive trajectory dataset, the task of mining spatio-temporal reachable regions aims at finding which road segments are reachable from these locations within a given temporal period based on the historical trajectories. Determining such spatio-temporal reachable regions with high accuracy is vital for many urban applications, such as location-based recommendations and advertising. Traditional approaches to answering such queries essentially perform a distance-based range query over the given road network, which does not consider dynamic travel time at different time of day. By contrast, we propose a data-driven approach to formulate the problem as mining actual reachable regions based on a real historical trajectory dataset. Efficient algorithms for the Single-location spatio-temporal reachability Query (S-Query) and the Union-of-multi-location spatio-temporal reachability Query (U-Query) were presented in our recent work. In this paper, we extend the previous ideas by introducing a new type of reachability query with multiple sources, namely, the Intersection-of-multi-location spatio-temporal reachability Query (I-Query). As we demonstrate, answering I-Queries efficiently is generally more computationally challenging than answering either S-Queries or U-Queries because I-Queries involve complicated intersect conditions. We propose two new algorithms called the Intersection-of-Multi-location Query Maximum Bounding region search (I-MQMB) algorithm and the I-Query Trace Back Search (I-TBS) algorithm to efficiently answer I-Queries, which utilize an indexing schema composed of a spatio-temporal index and a connection index. We evaluate our system extensively by using a large-scale real taxi trajectory dataset that records taxi rides in Shenzhen, China. Our results demonstrate that the proposed approach reduces the running time of I-Queries by 50 percent on average compared to the baseline method.

Identifying urban gathering events is an important problem due to challenges it brings to urban management. In our prior work, 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 two large real-world datasets and an event simulator. The experiments show the proposed model significantly improves the prediction accuracy and timeliness of forecasting gathering events, resulting in average precision of 0.91 and recall of 0.67 as opposed to 0.74 and 0.50 of H-VIGO-GIS.

Skyline computation, aiming at identifying a set of skyline points that are not dominated by any other point, is particularly useful for multi-criteria data analysis and decision making. Traditional skyline computation, however, is inadequate to answer queries that need to analyze not only individual points but also groups of points. To address this gap, we generalize the original skyline definition to the novel group-based skyline (G-Skyline), which represents Pareto optimal groups that are not dominated by other groups. In order to compute G-Skyline groups consisting ofspoints efficiently, we present a novel structure that represents the points in a directed skyline graph and captures the dominance relationships among the points based on the firstsskyline layers. We propose efficient algorithms to compute the firstsskyline layers. We then present two heuristic algorithms to efficiently compute the G-Skyline groups: the point-wise algorithm and the unit group-wise algorithm, using various pruning strategies. We observe that the number of G-Skyline groups of a dataset can be significantly large, we further propose the top-krepresentative G-Skyline groups based on the number of dominated points and the number of dominated groups and present efficient algorithms for computing them. The experimental results on the real NBA dataset and the synthetic datasets show that G-Skyline is interesting and useful, and our algorithms are efficient and scalable.

Skyline queries are important in many application domains. In this paper, we propose a novel structure Skyline Diagram, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. All query points in the same skyline polyomino have the same skyline query results. Similar to kth-order Voronoi diagram commonly used to facilitate k nearest neighbor (kNN) queries, skyline diagram can be used to facilitate skyline queries and many other applications. However, it may be computationally expensive to build the skyline diagram. By exploiting some interesting properties of skyline, we present several efficient algorithms for building the diagram with respect to three kinds of skyline queries, quadrant, global, and dynamic skylines. In addition, we propose an approximate skyline diagram which can significantly reduce the space cost. Experimental results on both real and synthetic datasets show that our algorithms are efficient and scalable.

Learning to make optimal decisions is a common yet complicated task. While computer agents can learn to make decisions by running reinforcement learning (RL), it remains unclear how human beings learn. In this paper, we perform the first data-driven case study on taxi drivers to validate whether humans mimic RL to learn. We categorize drivers into three groups based on their performance trends and analyze the correlations between human drivers and agents trained using RL. We discover that drivers that become more efficient at earning over time exhibit similar learning patterns to those of agents, whereas drivers that become less efficient tend to do the opposite. Our study (1) provides evidence that some human drivers do adapt RL when learning, (2) enhances the deep understanding of taxi drivers' learning strategies, (3) offers a guideline for taxi drivers to improve their earnings, and (4) develops a generic analytical framework to study and validate human learning strategies.

Urban traffic status (e.g., traffic speed and volume) is highly dynamic in nature, namely, varying across space and evolving over time. Thus, predicting such traffic dynamics is of great importance to urban development and transportation management. However, it is very challenging to solve this problem due to spatial-temporal dependencies and traffic uncertainties. In this paper, we solve the traffic dynamics prediction problem from Bayesian meta-learning perspective and propose a novel continuous spatial-temporal meta-learner (cST-ML), which is trained on a distribution of traffic prediction tasks segmented by historical traffic data with the goal of learning a strategy that can be quickly adapted to related but unseen traffic prediction tasks. cST-ML tackles the traffic dynamics prediction challenges by advancing the Bayesian black-box meta-learning framework through the following new points: 1) cST-ML captures the dynamics of traffic prediction tasks using variational inference; 2) cST-ML has novel designs in architecture, where CNN and LSTM are embedded to capture the spatial-temporal dependencies between traffic status and traffic related features; 3) novel training and testing algorithms for cST-ML are designed. We also conduct experiments on two real-world traffic datasets (taxi inflow and traffic speed) to evaluate our proposed cST-ML. The experimental results verify that cST-ML can significantly improve the urban traffic prediction performance and outperform all baseline models.

Mobile sensing and information technology have enabled us to collect a large amount of mobility data from human decision-makers, for example, GPS trajectories from taxis, Uber cars, and passenger trip data of taking buses and trains. Understanding and learning human decision-making strategies from such data can potentially promote individual's well-being and improve the transportation service quality. Existing works on human strategy learning, such as inverse reinforcement learning, all model the decision-making process as a Markov decision process, thus assuming the Markov property. In this work, we show that such Markov property does not hold in real-world human decision-making processes. To tackle this challenge, we develop a Trajectory Generative Adversarial Imitation Learning (TrajGAIL) framework. It captures the long-term decision dependency by modeling the human decision processes as variable length Markov decision processes (VLMDPs), and designs a deep-neural-network-based framework to inversely learn the decision-making strategy from the human agent's historical dataset. We validate our framework using two real world human-generated spatial-temporal datasets including taxi driver passenger-seeking decision data and public transit trip data. Results demonstrate significant accuracy improvement in learning human decision-making strategies, when comparing to baselines with Markov property assumptions.

To make daily decisions, human agents devise their own "strategies" governing their mobility dynamics (e.g., taxi drivers have preferred working regions and times, and urban commuters have preferred routes and transit modes). Recent research such as generative adversarial imitation learning (GAIL) demonstrates successes in learning human decision-making strategies from their behavior data using deep neural networks (DNNs), which can accurately mimic how humans behave in various scenarios, e.g., playing video games, etc. However, such DNN-based models are "black box" models in nature, making it hard to explain what knowledge the models have learned from human, and how the models make such decisions, which was not addressed in the literature of imitation learning. This paper addresses this research gap by proposing xGAIL, the first explainable generative adversarial imitation learning framework. The proposed xGAIL framework consists of two novel components, including Spatial Activation Maximization (SpatialAM) and Spatial Randomized Input Sampling Explanation (SpatialRISE), to extract both global and local knowledge from a well-trained GAIL model that explains how a human agent makes decisions. Especially, we take taxi drivers' passenger-seeking strategy as an example to validate the effectiveness of the proposed xGAIL framework. Our analysis on a large-scale real-world taxi trajectory data shows promising results from two aspects: i) global explainable knowledge of what nearby traffic condition impels a taxi driver to choose a particular direction to find the next passenger, and ii) local explainable knowledge of what key (sometimes hidden) factors a taxi driver considers when making a particular decision.

Given the historical movement trajectories of a set of individual human agents (e.g., pedestrians, taxi drivers) and a set of new trajectories claimed to be generated by a specific agent, the Human Mobility Signature Identification (HuMID) problem aims at validating if the incoming trajectories were indeed generated by the claimed agent. This problem is important in many real-world applications such as driver verification in ride-sharing services, risk analysis for auto insurance companies, and criminal identification. Prior work on identifying human mobility behaviors requires additional data from other sources besides the trajectories, e.g., sensor readings in the vehicle for driving behavior identification. However, these data might not be universally available and is costly to obtain. To deal with this challenge, in this work, we make the first attempt to match identities of human agents only from the observed location trajectory data by proposing a novel and efficient framework named Spatio-temporal Siamese Networks (ST-SiameseNet). For each human agent, we extract a set of profile and online features from his/her trajectories. We train ST-SiameseNet to predict the mobility signature similarity between each pair of agents, where each agent is represented by his/her trajectories and the extracted features. Experimental results on a real-world taxi trajectory dataset show that our proposed ST-SiamesNet can achieve an $F_1$ score of $0.8508$, which significantly outperforms the state-of-the-art techniques.

Given an urban development plan and the historical traffic observations over the road network, the Conditional Urban Traffic Estimation problem aims to estimate the resulting traffic status prior to the deployment of the plan. This problem is of great importance to urban development and transportation management, yet is very challenging because the plan would change the local travel demands drastically and the new travel demand pattern might be unprecedented in the historical data. To tackle these challenges, we propose a novel Conditional Urban Traffic Generative Adversarial Network (Curb-GAN), which provides traffic estimations in consecutive time slots based on different (unprecedented) travel demands, thus enables urban planners to accurately evaluate urban plans before deploying them. The proposed Curb-GAN adopts and advances the conditional GAN structure through a few novel ideas: (1) dealing with various travel demands as the "conditions" and generating corresponding traffic estimations, (2) integrating dynamic convolutional layers to capture the local spatial auto-correlations along the underlying road networks, (3) employing self-attention mechanism to capture the temporal dependencies of the traffic across different time slots. Extensive experiments on two real-world spatio-temporal datasets demonstrate that our Curb-GAN outperforms major baseline methods in estimation accuracy under various conditions and can produce more meaningful estimations.

Public transports, such as subway lines and buses, offer affordable ride-sharing services and reduce the road network traffic. Extracting passengers’ preferences from their public transit choices is important to city planners but technically non-trivial. When traveling by taking public transits, passengers make sequences of transit choices, and their rewards are usually influenced by other passengers’ choices. This process can be modeled as a Markov Game (MG). In this paper, we make the first effort to model travelers’ preferences of making transit choices using MGs. Based on the discovery that passengers usually do not change their policies, we propose novel algorithms to extract reward functions from the observed deterministic equilibrium joint policy of all agents in a general-sum MG to infer travelers’ preferences. First, we assume we have the access to the entire joint policy. We characterize the set of all reward functions for which the given joint policy is a Nash equilibrium policy. In order to remove the degeneracy of the solution, we then attempt to pick reward functions so as to maximize the sum of the deviation between the the observed policy and the sub-optimal policy of each agent. This results in a skillfully solvable linear programming algorithm for the multi-agent inverse reinforcement learning (MA-IRL) problem. Then, we deal with the case where we have access to the equilibrium joint policy through a set of actual trajectories. We propose an iterative algorithm inspired by single-agent apprenticeship learning algorithms and the cyclic coordinate descent approach. We evaluate the proposed algorithms on both a simple Grid Game and a unique real-world dataset (from Shenzhen, China). Results show that when we have access to the full policy, our algorithm can efficiently recover most of the reward structure, especially the interaction of agents. In the case where we only have access to a set of sampled expert trajectories, our algorithm can provide an explanation of the expert trajectories. Measured with respect to the experts’ unknown reward function, the performance of the policy output by our algorithm is close to that of the expert policy.

Many real-world human behaviors can be modeled and characterized as sequential decision-making processes, such as a taxi driver’s choices of working regions and times. Each driver possesses unique preferences on the sequential choices over time and improves the driver’s working efficiency. Understanding the dynamics of such preferences helps accelerate the learning process of taxi drivers. Prior works on taxi operation management mostly focus on finding optimal driving strategies or routes, lacking in-depth analysis on what the drivers learned during the process and how they affect the performance of the driver. In this work, we make the first attempt to establish Dynamic Human Preference Analytics. We inversely learn the taxi drivers’ preferences from data and characterize the dynamics of such preferences over time. We extract two types of features (i.e., profile features and habit features) to model the decision space of drivers. Then through inverse reinforcement learning, we learn the preferences of drivers with respect to these features. The results illustrate that self-improving drivers tend to keep adjusting their preferences to habit features to increase their earning efficiency while keeping the preferences to profile features invariant. However, experienced drivers have stable preferences over time. The exploring drivers tend to randomly adjust the preferences over time.

We present SkyRec (Skyline Recommender), a recommendation toolkit for finding optimal groups based on the notion of group skyline. Skyline computation, aiming at identifying a set of skyline points that are not dominated by any other point, is particularly useful for multi-criteria data analysis and decision-making. Traditional skyline computation, however, is inadequate to answer queries that need to analyze not only individual points but also groups of points. o address this gap, SkyRec finds Pare to optimal groups with two group skyline models: G-Skyline [3] and Sum-Skyline [2]. SkyRecre turns Pare to optimal groups with group size k that are not dom-inated by any other group with the same group size. Users can examine the results of the group skyline based recommendation compared to traditional top-k and skyline based recommendation and how different group skyline notions differ from each other. Although we demonstrate Sky Rec for hotel reservation in this paper, it can be applied to various decision-making applications

The rapid progress of urbanization has expedited the process of urban planning, e.g., new residential, commercial areas, which in turn boosts the local travel demand. We propose a novel "off-deployment traffic estimation problem", namely, to foresee the traffic condition changes of a region prior to the deployment of a construction plan. This problem is important to city planners to evaluate and develop urban deployment plans. However, this task is challenging. Traditional traffic estimation approaches lack the ability to solve this problem, since no data about the impact can be collected before the deployment and old data fails to capture the traffic pattern changes. In this paper, we define the off-deployment traffic estimation problem as a traffic generation problem, and develop a novel deep generative model TrafficGAN that captures the shared patterns across spatial regions of how traffic conditions evolve according to travel demand changes and underlying road network structures. In particular, TrafficGAN captures the road network structures through a dynamic filter in the dynamic convolutional layer. We evaluate our TrafficGAN using a large-scale traffic data collected from Shenzhen, China. Results show that TrafficGAN can more accurately estimate the traffic conditions compared with all baselines.

Smart passenger-seeking strategies employed by taxi drivers contribute not only to drivers' incomes, but also higher quality of service passengers received. Therefore, understanding taxi drivers' behaviors and learning the good passenger-seeking strategies are crucial to boost taxi drivers' well-being and public transportation quality of service. However, we observe that drivers' preferences of choosing which area to find the next passenger are diverse and dynamic across locations and drivers. It is hard to learn the location-dependent preferences given the partial data (i.e., an individual driver's trajectory may not cover all locations). In this paper, we make the first attempt to develop conditional generative adversarial imitation learning (cGAIL) model, as a unifying collective inverse reinforcement learning framework that learns the driver's decision-making preferences and policies by transferring knowledge across taxi driver agents and across locations. Our evaluation results on three months of taxi GPS trajectory data in Shenzhen, China, demonstrate that the driver's preferences and policies learned from cGAIL are on average 34.7% more accurate than those learned from other state-of-the-art baseline approaches.

Many real world human behaviors can be modeled and characterized as sequential decision making processes, such as taxi driver's choices of working regions and times. Each driver possesses unique preferences on the sequential choices over time and improves their working efficiency. Understanding the dynamics of such preferences helps accelerate the learning process of taxi drivers. Prior works on taxi operation management mostly focus on finding optimal driving strategies or routes, lacking in-depth analysis on what the drivers learned during the process and how they affect the performance of the driver. In this work, we make the first attempt to inversely learn the taxi drivers' preferences from data and characterize the dynamics of such preferences over time. We extract two types of features, i.e., profile features and habit features, to model the decision space of drivers. Then through inverse reinforcement learning we learn the preferences of drivers with respect to these features. The results illustrate that self-improving drivers tend to keep adjusting their preferences to habit features to increase their earning efficiency, while keeping the preferences to profile features invariant. On the other hand, experienced drivers have stable preferences over time.

Given a set of objects O (such as hotels), each can be represented as a point in a multi-dimensional feature space where each dimension corresponds to one attribute of the objects (such as price). Given the preference of a customer, the objects in O not dominated by any other object (i.e., beat in all dimensions) are those worthy to be further considered. Such objects are known as skyline objects in database community. Suppose we have an object o ∈ O. If o is a skyline point, other skyline objects are called peers of o. If o is not a skyline object, it must be dominated by some skyline objects which are called dominators of o. Given a large number of user preferences, an interesting problem is to identify the most frequent peer/dominator (MFP/MFD) of o. The MFP/MFD search has unique values in competitor analysis of various information systems. However, it is a challenging task because of the complexity to process a large number of user preferences. In this work, we provide robust solutions including exact and approximate methods. While the exact solutions explore the dominance relationship in the feature space, the approximate solutions are based on sampling techniques with theoretical bounds. We did extensive tests on large data sets which are up to 100 million user preferences generated from commercial surveys. The test resutls demonstrate the exact algorithms outperform various baseline algorithms significantly, and the approximate algorithms make further improvement by one order of magnitude with 90-98 percent accuracy.

Skyline queries are important in many application domains. In this paper, we propose a novel structure Skyline Diagram, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. All query points in the same skyline polyomino have the same skyline query results. Similar to k^th-order Voronoi diagram commonly used to facilitate k nearest neighbor (kNN) queries, skyline diagram can be used to facilitate skyline queries and many other applications. However, it may be computationally expensive to build the skyline diagram. By exploiting some interesting properties of skyline, we present several efficient algorithms for building the diagram with respect to three kinds of skyline queries, quadrant, global, and dynamic skylines. Experimental results on both real and synthetic datasets show that our algorithms are efficient and scalable.

Public transits, such as buses and subway lines, offer affordable ride-sharing services and reduce the road network traffic, thus have significant impacts in mitigating the urban traffic congestion problem. However, it is non-trivial to evaluate a new transit plan, such as a new bus route or a new subway line, of its future ridership prior to actual deployment, since the travel preferences of passengers along the planned routes may vary. In this paper, we make the first attempt to model passengers' preferences of making various transit choices using a Markov Decision Process (MDP). Moreover, we develop a novel inverse preference learning algorithm to infer the passengers' preferences and predict the future human behavior changes, e.g., ridership, of a new urban transit plan before its deployment. We validate our proposed framework using a unique real-world dataset (from Shenzhen, China) with three subway lines opened during the data time span. With the data collected from both before and after the transit plan deployments, Our evaluation results demonstrated that the proposed framework can predict the ridership with only 19.8% relative error, which is 23%-51% lower than other baseline approaches.

Rapid urbanization has posed significant burden on urban transportation infrastructures. In today's cities, both private and public transits have clear limitations to fulfill passengers' needs for quality of experience (QoE): Public transits operate along fixed routes with long wait time and total transit time; Private transits, such as taxis, private shuttles and ride-hailing services, provide point-to-point transits with high trip fare. In this paper, we propose CityLines, a transformative urban transit system, employing hybrid hub-and-spoke transit model with shared shuttles. Analogous to Airlines services, the proposed CityLines system routes urban trips among spokes through a few hubs or direct paths, with travel time as short as private transits and fare as low as public transits. CityLines allows both point-to-point connection to improve the passenger QoE, and hub-and-spoke connection to reduce the system operation cost. Our evaluation results show that CityLines framework can achieve both short travel time and high ride-sharing ratio.

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 realtime 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.

Mining spatio-temporal reachable regions aims to find a set of road segments from massive trajectory data, that are reachable from a user-specified location and within a given temporal period. Accurately extracting such spatiotemporal reachable area is vital in many urban applications, e.g., (i) location-based recommendation, (ii) location-based advertising, and (iii) business coverage analysis. The traditional approach of answering such queries essentially performs a distance-based range query over the given road network, which have two main drawbacks: (i) it only works with the physical travel distances, where the users usually care more about dynamic traveling time, and (ii) it gives the same result regardless of the querying time, where the reachable area could vary significantly with different traffic conditions. Motivated by these observations, we propose a data-driven approach to formulate the problem as mining actual reachable region based on real historical trajectory dataset. The main challenge in our approach is the system efficiency, as verifying the reachability over the massive trajectories involves huge amount of disk I/Os. In this paper, we develop two indexing structures: 1) spatio-temporal index (ST-Index) and 2) connection index (Con-Index) to reduce redundant trajectory data access operations. We also propose a novel query processing algorithm with: 1) maximum bounding region search, which directly extracts a small searching region from the index structure and 2) trace back search, which refines the search results from the previous step to find the final query result. Moreover, our system can also efficiently answer the spatio-temporal reachability query with multiple query locations by skipping the overlapped area search. We evaluate our system extensively using a large-scale real taxi trajectory data in Shenzhen, China, where results demonstrate that the proposed algorithms can reduce 50%-90% running time over baseline algorithms.

It has been estimated that the cumulative sales of Electric Vehicles (EVs) will be up to 5.9 million and the stock of EVs will be up to 20 million by 2020 [1]. As the number of EVs is expanding, there is a growing need for widely distributed, publicly accessible, EV charging facilities. The public EV Chargers (EVCs) are expected to be found and will be needed where there is on-street parking, at taxi stands, in parking lots at places of employment, hotels, airports, shopping centres, convenience shops, fast food restaurants, and coffee houses, etc. In this work, we aim to optimize the distribution of public EVCs across the city such that (i) the overall revenue generated by the EVCs is maximized, subject to (ii) the overall driver discomfort (e.g., queueing time) for EV charging is minimized. This is the first study on EVC distribution where EVCs are assumed to be installed in almost all regions across a city. The problem is formulated using a bilevel optimization model. We propose an alternating framework to solve it and have proved that a local minima is achievable. Moreover, this work introduces novel methods to extract information to understand the discomfort of petroleum car drivers, EV charging demands, parking time and parking fees across the city. The source data explored include the trajectories of taxis, the distribution of petroleum stations and various local features. The empirical study uses the real data sets from Shenzhen City, one of the largest cities in China. The extensive tests verify the superiority of the proposed bilevel optimization model in all aspects.

Skyline is a set of points that are not dominated by any other point. Given uncertain objects, probabilistic skyline has been studied which computes objects with high probability of being skyline. While useful for selecting individual objects, it is not sufficient for scenarios where we wish to compute a subset of skyline objects, i.e., a skyline set. In this paper, we generalize the notion of probabilistic skyline to probabilistic k-skyline sets (Pk-SkylineSets) which computes k-object sets with high probability of being skyline set. We present an efficient algorithm for computing probabilistic k-skyline sets. It uses two heuristic pruning strategies and a novel data structure based on the classic layered range tree to compute the skyline set probability for each instance set with a worst-case time bound. The experimental results on the real NBA dataset and the synthetic datasets show that Pk-SkylineSets is interesting and useful, and our algorithms are efficient and scalable.

Indexing moving objects has been extensively studied in the past decades. In most real world applications, the moving objects exhibit particular patterns on their velocities. For example, velocities of vehicles in city road networks usually show patterns on both directions and values. Velocity-based partitioning techniques have been proved effective in improving query performances of moving object indexes. This demo presents VPIndexer, a toolkit for visualizing comparison of three velocity-based partitioning algorithms: VMBR-based partitioning, DVA-based partitioning and our recently proposed speed-based partitioning techniques. VPIndexer uses the Bx-tree and the TPR*-tree as the baseline approaches.

Electric vehicles (EVs) have undergone an explosive increase over recent years, due to the unparalleled advantages over gasoline cars in green transportation and cost efficiency. Such a drastic increase drives a growing need for widely deployed publicly accessible charging stations. Thus, how to strategically deploy the charging stations and charging points becomes an emerging and challenging question to urban planners and electric utility companies. In this paper, by analyzing a large scale electric taxi trajectory data, we make the first attempt to investigate this problem. We develop an optimal charging station deployment (OCSD) framework that takes the historical EV taxi trajectory data, road map data, and existing charging station information as input, and performs optimal charging station placement (OCSP) and optimal charging point assignment (OCPA). The OCSP and OCPA optimization components are designed to minimize the average time to the nearest charging station, and the average waiting time for an available charging point, respectively. To evaluate the performance of our OCSD framework, we conduct experiments on one-month real EV taxi trajectory data. The evaluation results demonstrate that our OCSD framework can achieve a 26%–94% reduction rate on average time to find a charging station, and up to two orders of magnitude reduction on waiting time before charging, over baseline methods. Moreover, our results reveal interesting insights in answering the question: “Super or small stations?”: When the number of deployable charging points is sufficiently large, more small stations are preferred; and when there are relatively few charging points to deploy, super stations is a wiser choice.

Skyline computation, aiming at identifying a set of skyline points that are not dominated by any other point, is particularly useful for multi-criteria data analysis and decision making. Traditional skyline computation, however, is inadequate to answer queries that need to analyze not only individual points but also groups of points. To address this gap, we generalize the original skyline definition to the novel group-based skyline (G-Skyline), which represents Pareto optimal groups that are not dominated by other groups. In order to compute G-Skyline groups consisting of k points efficiently, we present a novel structure that represents the points in a directed skyline graph and captures the dominance relationships among the points based on the first k skyline layers. We propose efficient algorithms to compute the first k skyline layers. We then present two heuristic algorithms to efficiently compute the G-Skyline groups: the point-wise algorithm and the unit group-wise algorithm, using various pruning strategies. The experimental results on the real NBA dataset and the synthetic datasets show that G-Skyline is interesting and useful, and our algorithms are efficient and scalable.