A considerable amount of mobility data has been accumulated due to the proliferation of location-based services. Nevertheless, compared with mobility data from transportation systems like the GPS module in taxis, this kind of data is commonly sparse in terms of individual trajectories in the sense that users do not access mobile services and contribute their data all the time. Consequently, the sparsity inevitably weakens the practical value of the data even if it has a high user penetration rate. To solve this problem, we propose a novel attentional neural network-based model, named AttnMove, to densify individual trajectories by recovering unobserved locations at a fine-grained spatial-temporal resolution. To tackle the challenges posed by sparsity, we design various intra- and inter- trajectory attention mechanisms to better model the mobility regularity of users and fully exploit the periodical pattern from long-term history. In addition, to guarantee the robustness of the generated trajectories to avoid harming downstream applications, we also exploit the Bayesian approximate neural network to estimate the uncertainty of each imputation. As a result, locations generated by the model with high uncertainty will be excluded. We evaluate our model on two real-world datasets, and extensive results demonstrate the performance gain compared with the state-of-the-art methods. In-depth analyses of each design of our model have been conducted to understand their contribution. We also show that, by providing high-quality mobility data, our model can benefit a variety of mobility-oriented downstream applications.

Urban time series data forecasting featuring significant contributions to sustainable development is widely studied as an essential task of the smart city. However, with the dramatic and rapid changes in the world environment, the assumption that data obey Independent Identically Distribution is undermined by the subsequent changes in data distribution, known as concept drift, leading to weak replicability and transferability of the model over unseen data. To address the issue, previous approaches typically retrain the model, forcing it to fit the most recent observed data. However, retraining is problematic in that it leads to model lag, consumption of resources, and model re-invalidation, causing the drift problem to be not well solved in realistic scenarios. In this study, we propose a new urban time series prediction model for the concept drift problem, which encodes the drift by considering the periodicity in the data and makes on-the-fly adjustments to the model based on the drift using a meta-dynamic network. Experiments on real-world datasets show that our design significantly outperforms state-of-the-art methods and can be well generalized to existing prediction backbones by reducing their sensitivity to distribution changes.

Crowd flow prediction is of great importance in a wide range of applications from urban planning, traffic control to public safety. It aims at predicting the inflow (the traffic of crowds entering a region in a given time interval) and outflow (the traffic of crowds leaving a region for other places) of each region in the city with knowing the historical flow data. In this article, we propose DeepSTN+, a deep learning-based convolutional model, to predict crowd flows in the metropolis. First, DeepSTN+ employs the ConvPlus structure to model the long-range spatial dependence among crowd flows in different regions. Further, PoI distributions and time factor are combined to express the effect of location attributes to introduce prior knowledge of the crowd movements. Finally, we propose a temporal attention-based fusion mechanism to stabilize the training process, which further improves the performance. Extensive experimental results based on four real-life datasets demonstrate the superiority of our model, i.e., DeepSTN+ reduces the error of the crowd flow prediction by approximately 10%–21% compared with the state-of-the-art baselines.

A considerable amount of mobility data has been accumulated due to the proliferation of location-based service. Nevertheless, compared with mobility data from transportation systems like the GPS module in taxis, this kind of data is commonly sparse in terms of individual trajectories in the sense that users do not access mobile services and contribute their data all the time. Consequently, the sparsity inevitably weakens the practical value of the data even it has a high user penetration rate. To solve this problem, we propose a novel attentional neural network-based model, named AttnMove, to densify individual trajectories by recovering unobserved locations at a fine-grained spatial-temporal resolution. To tackle the challenges posed by sparsity, we design various intra- and inter- trajectory attention mechanisms to better model the mobility regularity of users and fully exploit the periodical pattern from long-term history. We evaluate our model on two real-world datasets, and extensive results demonstrate the performance gain compared with the state-of-the-art methods. This also shows that, by providing high-quality mobility data, our model can benefit a variety of mobility-oriented down-stream applications.

Traffic prediction is a crucial task in many real-world applications. The task is challenging due to the implicit and dynamic spatio-temporal dependencies among traffic data. On the one hand, the spatial dependencies among traffic flows are latent and fluctuate with environmental conditions. On the other hand, the temporal dependencies among traffic flows also vary significantly over time and locations. In this paper, we propose Adaptive Spatio-Temporal Convolutional Network (ASTCN) to tackle these challenges. First, we propose a spatial graph learning module that learns the dynamic spatial relations among traffic data based on multiple influential factors. Furthermore, we design an adaptive temporal convolution module that captures complex temporal traffic dependencies with environment-aware dynamic filters. We conduct extensive experiments on three real-world traffic datasets. The results demonstrate that the proposed ASTCN consistently outperforms state-of-the-arts.

We collected 92,832 user-contributed and publicly available family trees from rootsweb.com, including 250 million individuals who were born in North America and Europe between 1630 and 1930. We cleaned and connected the family trees to create a population-scale and longitudinal family tree dataset using a workflow of data collection and cleaning, geocoding, fuzzy record linkage and a relation-based iterative search for connecting trees and deduplication of records. Given the largest connected component of nearly 40 million individuals, and a total of 80 million individuals, we generated, to date, the largest population-scale and longitudinal geo-social network over centuries. We evaluated the representativeness of the family tree dataset for historical population demography and mobility by comparing the data to the 1880 Census. Our results showed that the family trees were biased towards males, the elderly, farmers, and native-born white segments of the population. Individuals were highly mobile – in our 1880 sample of parent-child pairs where both were born in the U.S., 47% were born in different states. Our findings agreed with prior studies that people migrated from East to West in horizontal bands, and the trend was reflected in the dialects and regional structure of the U.S.

Crowd flow prediction is an essential task benefiting a wide range of applications for the transportation system and public safety. However, it is a challenging problem due to the complex spatio-temporal dependence and the complicated impact of urban structure on the crowd flow patterns. In this article, we propose a novel framework, 3- D imensional G raph C onvolution N etwork (3DGCN), to predict citywide crowd flow. We first model it as a dynamic spatio-temporal graph prediction problem, where each node represents a region with time-varying flows, and each edge represents the origin–destination (OD) flow between its corresponding regions. As such, OD flows among regions are treated as a proxy for the spatial interactions among regions. To tackle the complex spatio-temporal dependence, our proposed 3DGCN can model the correlation among graph spatial and temporal neighbors simultaneously. To learn and incorporate urban structures in crowd flow prediction, we design the GCN aggregator to be learned from both crowd flow prediction and region function inference at the same time. Extensive experiments with real-world datasets in two cities demonstrate that our model outperforms state-of-the-art baselines by 9.6%∼19.5% for the next-time-interval prediction.

Population flow prediction is one of the most fundamental components in many applications from urban management to transportation schedule. It is challenging due to the complicated spatial-temporal correlation.While many studies have been done in recent years, they fail to simultaneously and effectively model the spatial correlation and temporal variations among population flows. In this paper, we propose Convolution based Sequential and Cross Network (CSCNet) to solve them. On the one hand, we design a CNN based sequential structure with progressively merging the flow features from different time in different CNN layers to model the spatial-temporal information simultaneously. On the other hand, we make use of the transition flow as the proxy to efficiently and explicitly capture the dynamic correlation between different types of population flows. Extensive experiments on 4 datasets demonstrate that CSCNet outperforms the state-of-the-art baselines by reducing the prediction error around 7.7%∼10.4%.

Map matching is important in many trajectory based applications like route optimization and traffic schedule, etc. As the widely used methods, Hidden Markov Model and its variants are well studied to provide accurate and efficient map matching service. However, HMM based methods fail to utilize the value of enormous trajectory big data, which are useful for the map matching task. Furthermore, with many following-up works, they are still easily influenced by the noisy records, which are very common in the real system. To solve these problems, we revisit the map matching task from the data perspective, and propose to utilize the great power of data to help solve these problems. We build a deep learning based model to utilize all the trajectory data for joint training and knowledge sharing. With the help of embedding techniques and sequence learning model with attention enhancement, our system does the map matching in the latent space, which is tolerant to the noise in the physical space. Extensive experiments demonstrate that our model outperforms the widely used HMM based methods more than 10% (absolute accuracy) and works robustly in the noisy settings in the meantime.

Modeling people's activities in the urban space is a crucial socio-economic task but extremely challenging due to the deficiency of suitable methods. To model the temporal dynamics of human activities concisely and specifically, we present State-sharing Hidden Markov Model (SSHMM). First, it extracts the urban states from the whole city, which captures the volume of population flows as well as the frequency of each type of Point of Interests (PoIs) visited. Second, it characterizes the urban dynamics of each urban region as the state transition on the shared-states, which reveals distinct daily rhythms of urban activities. We evaluate our method via a large-scale real-life mobility dataset and results demonstrate that SSHMM learns semantics-rich urban dynamics, which are highly correlated with the functions of the region. Besides, it recovers the urban dynamics in different time slots with an error of 0.0793, which outperforms the general HMM by 54.2%.

With the flourishing of location based social networks, posting check-ins has become a common practice to document one's daily life. Users usually do not consider check-in records as violations of their privacy. However, through analyzing two real-world check-in datasets, our study shows that check-in records are vulnerable to linkage attacks. To address this problem, we design a partition-and-group framework to integrate the information of check-ins and additional mobility data to attain a novel privacy criterion - kt, l-anonymity. It ensures adversaries with arbitrary background knowledge cannot use check-ins to re-identify users in other anonymous datasets or learning unreported mobility records. The proposed framework achieves favorable performance against state-of-art baseline in terms of improving check-in utility by 24% ~ 57% while providing stronger privacy guarantee at the same time. We believe this study will open a new angle in attaining both privacy-preserving and useful check-in services.

This paper presents a new methodology and evaluation experiments on the detection of spatial community structure in movements, which can reveal unknown spatial constructs and boundaries. While there are numerous existing approaches for community structure detection in spatial networks using either general-purpose methods or spatially modified extensions, they are usually designed and applied without controlled evaluation and understanding of their robustness in finding the underlying spatial communities. Towards addressing this challenge, we develop a new approach, Spatial Tabu Optimization for Community Structure (STOCS), which transforms trajectory data to a spatial network, integrates different community structure measures (e.g. modularity or edge ratio), and partitions the network into geographic regions to discover spatial communities in movements. We systematically evaluate and compare the new approach with existing methods using synthetic datasets that have known spatial community structures. Evaluation results show that general-purpose (non-spatial) methods are not robust for detecting spatial structures – their outcomes vary dramatically for the same data with different levels of spatial aggregation (resolution), data sampling, or data noise. STOCS is substantially more robust in discovering underlying spatial structures. Last, we present two case studies with animal movements and urban population movements to demonstrate the application of the approach.

This paper presents a new approach to flow mapping that extracts inherent patterns from massive geographic mobility data and constructs effective visual representations of the data for the understanding of complex flow trends. This approach involves a new method for origin-destination flow density estimation and a new method for flow map generalization, which together can remove spurious data variance, normalize flows with control population, and detect high-level patterns that are not discernable with existing approaches. The approach achieves three main objectives in addressing the challenges for analyzing and mapping massive flow data. First, it removes the effect of size differences among spatial units via kernel-based density estimation, which produces a measurement of flow volume between each pair of origin and destination. Second, it extracts major flow patterns in massive flow data through a new flow sampling method, which filters out duplicate information in the smoothed flows. Third, it enables effective flow mapping and allows intuitive perception of flow patterns among origins and destinations without bundling or altering flow paths. The approach can work with both point-based flow data (such as taxi trips with GPS locations) and area-based flow data (such as county-to-county migration). Moreover, the approach can be used to detect and compare flow patterns at different scales or in relatively sparse flow datasets, such as migration for each age group. We evaluate and demonstrate the new approach with case studies of U.S. migration data and experiments with synthetic data.

The relationship between two or more variables may change over the geographic space. The change can be in parameter values (e.g., regression coefficients) or even in relation forms (e.g., linear, quadratic, or exponential). Existing local spatial analysis methods often assume a relationship form (e.g., a linear regression model) for all regions and focus only on the change in parameter values. Therefore, they may not be able to discover local relationships of different forms simultaneously. This research proposes a nonparametric approach, a local entropy map, which does not assume a prior relationship form and can detect the existence of multivariate relationships regardless of their forms. The local entropy map calculates an approximation of the Rényi entropy for the multivariate data in each local region (in the geographic space). Each local entropy value is then converted to a p-value by comparing to a distribution of permutation entropy values for the same region. All p-values (one for each local region) are processed by several statistical tests to control the multiple-testing problem. Finally, the testing results are mapped and allow analysts to locate and interactively examine significant local relationships. The method is evaluated with a series of synthetic data sets and a real data set.

Spatial interactions (or flows), such as population migration and disease spread, naturally form a weighted location-to-location network (graph). Such geographically embedded networks (graphs) are usually very large. For example, the county-to-county migration data in the U.S. has thousands of counties and about a million migration paths. Moreover, many variables are associated with each flow, such as the number of migrants for different age groups, income levels, and occupations. It is a challenging task to visualize such data and discover network structures, multivariate relations, and their geographic patterns simultaneously. This paper addresses these challenges by developing an integrated interactive visualization framework that consists three coupled components: (1) a spatially constrained graph partitioning method that can construct a hierarchy of geographical regions (communities), where there are more flows or connections within regions than across regions; (2) a multivariate clustering and visualization method to detect and present multivariate patterns in the aggregated region-to-region flows; and (3) a highly interactive flow mapping component to map both flow and multivariate patterns in the geographic space, at different hierarchical levels. The proposed approach can process relatively large data sets and effectively discover and visualize major flow structures and multivariate relations at the same time. User interactions are supported to facilitate the understanding of both an overview and detailed patterns.

Regionalization is to divide a large set of spatial objects into a number of spatially contiguous regions while optimizing an objective function, which is normally a homogeneity (or heterogeneity) measure of the derived regions. This research proposes and evaluates a family of six hierarchical regionalization methods. The six methods are based on three agglomerative clustering approaches, including the single linkage, average linkage (ALK), and the complete linkage (CLK), each of which is constrained with spatial contiguity in two different ways (i.e. the first‐order constraining and the full‐order constraining). It is discovered that both the Full‐Order‐CLK and the Full‐Order‐ALK methods significantly outperform existing methods across four quality evaluations: the total heterogeneity, region size balance, internal variation, and the preservation of data distribution. Moreover, the proposed algorithms are efficient and can find the solution in O(n 2log n) time. With such data scalability, for the first time it is possible to effectively regionalize large data sets that have 10 000 or more spatial objects. A detailed comparison and evaluation of the six methods are carried out with the 2004 US presidential election data.

Population mobility, i.e. the movement and contact of individuals across geographic space, is one of the essential factors that determine the course of a pandemic disease spread. This research views both individual‐based daily activities and a pandemic spread as spatial interaction problems, where locations interact with each other via the visitors that they share or the virus that is transmitted from one place to another. The research proposes a general visual analytic approach to synthesize very large spatial interaction data and discover interesting (and unknown) patterns. The proposed approach involves a suite of visual and computational techniques, including (1) a new graph partitioning method to segment a very large interaction graph into a moderate number of spatially contiguous subgraphs (regions); (2) a reorderable matrix, with regions ‘optimally’ ordered on the diagonal, to effectively present a holistic view of major spatial interaction patterns; and (3) a modified flow map, interactively linked to the reorderable matrix, to enable pattern interpretation in a geographical context. The implemented system is able to visualize both people's daily movements and a disease spread over space in a similar way. The discovered spatial interaction patterns provide valuable insight for designing effective pandemic mitigation strategies and supporting decision‐making in time‐critical situations.

The research reported here integrates computational, visual, and cartographic methods to develop a geovisual analytic approach for exploring and understanding spatio-temporal and multivariate patterns. The developed methodology and tools can help analysts investigate complex patterns across multivariate, spatial, and temporal dimensions via clustering, sorting, and visualization. Specifically, the approach involves a self-organizing map, a parallel coordinate plot, several forms of reorderable matrices (including several ordering methods), a geographic small multiple display, and a 2-dimensional cartographic color design method. The coupling among these methods leverages their independent strengths and facilitates a visual exploration of patterns that are difficult to discover otherwise. The visualization system we developed supports overview of complex patterns and, through a variety of interactions, enables users to focus on specific patterns and examine detailed views. We demonstrate the system with an application to the IEEE InfoVis 2005 Contest data set, which contains time-varying, geographically referenced, and multivariate data for technology companies in the US.