Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> All digitizing methods, as a general rule, record lines with far more data than is necessary for accurate graphic reproduction or for computer analysis. Two algorithms to reduce the number of points required to represent the line and, if desired, produce caricatures, are presented and compared with the most promising methods so far suggested. Line reduction will form a major part of automated generalization. Regle generale, les methodes numeriques enregistrent des lignes avec beaucoup plus de donnees qu'il n'est necessaire a la reproduction graphique precise ou a la recherche par ordinateur. L'auteur presente deux algorithmes pour reduire le nombre de points necessaires pour representer la ligne et produire des caricatures si desire, et les compare aux methodes les plus prometteuses suggerees jusqu'ici. La reduction de la ligne constituera une partie importante de la generalisation automatique. <s> BIB001 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> In recent years, there has been an explosion of interest in mining time-series databases. As with most computer science problems, representation of the data is the key to efficient and effective solutions. One of the most commonly used representations is piecewise linear approximation. This representation has been used by various researchers to support clustering, classification, indexing and association rule mining of time-series data. A variety of algorithms have been proposed to obtain this representation, with several algorithms having been independently rediscovered several times. In this paper, we undertake the first extensive review and empirical comparison of all proposed techniques. We show that all these algorithms have fatal flaws from a data-mining perspective. We introduce a novel algorithm that we empirically show to be superior to all others in the literature. <s> BIB002 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> GPS based navigation and route guidance systems are becoming increasingly popular among bus operators, fleet managers and travelers. To provide this functionality, one has to have a GPS receiver, a digital map of the traveled network and software that can associate (match) the user's position with a location on the digital map. Matching the user's location has to be done even when the GPS location and the underlying digital map have inaccuracies and errors. There are several approaches for solving this map matching task. Some only match the user's location to the nearest street node while others are able to locate the user at specific location on the traveled street segment. In this paper a topologically based matching procedure is presented. The procedure was tested with low quality GPS data to assess its robustness. The performance of the algorithms was found to produce outstanding results <s> BIB003 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> The subject of this paper are algorithms for measuring the similarity of patterns of line segments in the plane, a standard problem in, e.g., computer vision, geographic information systems, etc. More precisely, we define feasible distance measures that reflect how close a given pattern H is to some part of a larger pattern G. These distance measures are generalizations of the well-known Frechet distance for curves. We first give an efficient algorithm for the case that H is a polygonal curve and G is a geometric graph. Then, slightly relaxing the definition of distance measure, we give an algorithm for the general case where both, H and G, are geometric graphs. <s> BIB004 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Moving object data handling has received a fair share of attention over recent years in the spatial database community. This is understandable as positioning technology is rapidly making its way into the consumer market, not only through the already ubiquitous cell phone but soon also through small, on-board positioning devices in many means of transport and in other types of portable equipment. It is thus to be expected that all these devices will start to generate an unprecedented data stream of time-stamped positions. Sooner or later, such enormous volumes of data will lead to storage, transmission, computation, and display challenges. Hence, the need for compression techniques. <s> BIB005 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> In location management, the trajectory represents the motion of a moving object in 3D space-time, i.e., a sequence (x, y, t). Unfortunately, location technologies, cannot guarantee error-freedom. Thus, map matching (a.k.a. snapping), matching a trajectory to the roads on the map, is necessary. We introduce a weight-based map matching method, and experimentally show that, for the offline situation, on average, our algorithm can get up to 94% correctness depending on the GPS sampling interval. <s> BIB006 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Vehicle tracking data is an essential "raw" material for a broad range of applications such as traffic management and control, routing, and navigation. An important issue with this data is its accuracy. The method of sampling vehicular movement using GPS is affected by two error sources and consequently produces inaccurate trajectory data. To become useful, the data has to be related to the underlying road network by means of map matching algorithms. We present three such algorithms that consider especially the trajectory nature of the data rather than simply the current position as in the typical map-matching case. An incremental algorithm is proposed that matches consecutive portions of the trajectory to the road network, effectively trading accuracy for speed of computation. In contrast, the two global algorithms compare the entire trajectory to candidate paths in the road network. The algorithms are evaluated in terms of (i) their running time and (ii) the quality of their matching result. Two novel quality measures utilizing the Frechet distance are introduced and subsequently used in an experimental evaluation to assess the quality of matching real tracking data to a road network. <s> BIB007 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Recent research on map matching algorithms for land vehicle navigation has been based on either a conventional topological analysis or a probabilistic approach. The input to these algorithms normally comes from the global positioning system (GPS) and digital map data. Although the performance of some of these algorithms is good in relatively sparse road networks, they are not always reliable for complex roundabouts, merging or diverging sections of motorways, and complex urban road networks. In high road density areas where the average distance between roads is less than 100 m, there may be many road patterns matching the trajectory of the vehicle reported by the positioning system at any given moment. Consequently, it may be difficult to precisely identify the road on which the vehicle is travelling. Therefore, techniques for dealing with qualitative terms such as likeliness are essential for map matching algorithms to identify a correct link. Fuzzy logic is one technique that is an effective way to deal... <s> BIB008 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Geographic information has spawned many novel Web applications where global positioning system (GPS) plays important roles in bridging the applications and end users. Learning knowledge from users' raw GPS data can provide rich context information for both geographic and mobile applications. However, so far, raw GPS data are still used directly without much understanding. In this paper, an approach based on supervised learning is proposed to automatically infer transportation mode from raw GPS data. The transportation mode, such as walking, driving, etc., implied in a user's GPS data can provide us valuable knowledge to understand the user. It also enables context-aware computing based on user's present transportation mode and design of an innovative user interface for Web users. Our approach consists of three parts: a change point-based segmentation method, an inference model and a post-processing algorithm based on conditional probability. The change point-based segmentation method was compared with two baselines including uniform duration based and uniform length based methods. Meanwhile, four different inference models including Decision Tree, Bayesian Net, Support Vector Machine (SVM) and Conditional Random Field (CRF) are studied in the experiments. We evaluated the approach using the GPS data collected by 45 users over six months period. As a result, beyond other two segmentation methods, the change point based method achieved a higher degree of accuracy in predicting transportation modes and detecting transitions between them. Decision Tree outperformed other inference models over the change point based segmentation method. <s> BIB009 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> This paper presents a method for reliable matching of position and orientation measurements from a standard GPS receiver to a digital map. By incorporating road network topology in the matching process using a hidden Markov model, an optimum position and orientation history can be computed from a sequence of GPS measurements. Increased robustness is achieved by introducing constraints for vehicular motion in an extended Kalman filter and by reconstructing the original road network from the digital map using cubic spline interpolation. The proposed method delivers robust matching results for standard inner-city scenarios and gives a reliable estimate of the optimal position history even for severely disturbed GPS measurements. <s> BIB010 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> The problem of matching measured latitude/longitude points to roads is becoming increasingly important. This paper describes a novel, principled map matching algorithm that uses a Hidden Markov Model (HMM) to find the most likely road route represented by a time-stamped sequence of latitude/longitude pairs. The HMM elegantly accounts for measurement noise and the layout of the road network. We test our algorithm on ground truth data collected from a GPS receiver in a vehicle. Our test shows how the algorithm breaks down as the sampling rate of the GPS is reduced. We also test the effect of increasing amounts of additional measurement noise in order to assess how well our algorithm could deal with the inaccuracies of other location measurement systems, such as those based on WiFi and cell tower multilateration. We provide our GPS data and road network representation as a standard test set for other researchers to use in their map matching work. <s> BIB011 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Map-matching is the process of aligning a sequence of observed user positions with the road network on a digital map. It is a fundamental pre-processing step for many applications, such as moving object management, traffic flow analysis, and driving directions. In practice there exists huge amount of low-sampling-rate (e.g., one point every 2--5 minutes) GPS trajectories. Unfortunately, most current map-matching approaches only deal with high-sampling-rate (typically one point every 10--30s) GPS data, and become less effective for low-sampling-rate points as the uncertainty in data increases. In this paper, we propose a novel global map-matching algorithm called ST-Matching for low-sampling-rate GPS trajectories. ST-Matching considers (1) the spatial geometric and topological structures of the road network and (2) the temporal/speed constraints of the trajectories. Based on spatio-temporal analysis, a candidate graph is constructed from which the best matching path sequence is identified. We compare ST-Matching with the incremental algorithm and Average-Frechet-Distance (AFD) based global map-matching algorithm. The experiments are performed both on synthetic and real dataset. The results show that our ST-matching algorithm significantly outperform incremental algorithm in terms of matching accuracy for low-sampling trajectories. Meanwhile, when compared with AFD-based global algorithm, ST-Matching also improves accuracy as well as running time. <s> BIB012 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> User mobility has given rise to a variety of Web applications, in which the global positioning system (GPS) plays many important roles in bridging between these applications and end users. As a kind of human behavior, transportation modes, such as walking and driving, can provide pervasive computing systems with more contextual information and enrich a user's mobility with informative knowledge. In this article, we report on an approach based on supervised learning to automatically infer users' transportation modes, including driving, walking, taking a bus and riding a bike, from raw GPS logs. Our approach consists of three parts: a change point-based segmentation method, an inference model and a graph-based post-processing algorithm. First, we propose a change point-based segmentation method to partition each GPS trajectory into separate segments of different transportation modes. Second, from each segment, we identify a set of sophisticated features, which are not affected by differing traffic conditions (e.g., a person's direction when in a car is constrained more by the road than any change in traffic conditions). Later, these features are fed to a generative inference model to classify the segments of different modes. Third, we conduct graph-based postprocessing to further improve the inference performance. This postprocessing algorithm considers both the commonsense constraints of the real world and typical user behaviors based on locations in a probabilistic manner. The advantages of our method over the related works include three aspects. (1) Our approach can effectively segment trajectories containing multiple transportation modes. (2) Our work mined the location constraints from user-generated GPS logs, while being independent of additional sensor data and map information like road networks and bus stops. (3) The model learned from the dataset of some users can be applied to infer GPS data from others. Using the GPS logs collected by 65 people over a period of 10 months, we evaluated our approach via a set of experiments. As a result, based on the change-point-based segmentation method and Decision Tree-based inference model, we achieved prediction accuracy greater than 71 percent. Further, using the graph-based post-processing algorithm, the performance attained a 4-percent enhancement. <s> BIB013 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Matching a raw GPS trajectory to roads on a digital map is often referred to as the Map Matching problem. However, the occurrence of the low-sampling-rate trajectories (e.g. one point per 2 minutes) has brought lots of challenges to existing map matching algorithms. To address this problem, we propose an Interactive Voting-based Map Matching (IVMM) algorithm based on the following three insights: 1) The position context of a GPS point as well as the topological information of road networks, 2) the mutual influence between GPS points (i.e., the matching result of a point references the positions of its neighbors; in turn, when matching its neighbors, the position of this point will also be referenced), and 3) the strength of the mutual influence weighted by the distance between GPS points (i.e., the farther distance is the weaker influence exists). In this approach, we do not only consider the spatial and temporal information of a GPS trajectory but also devise a voting-based strategy to model the weighted mutual influences between GPS points. We evaluate our IVMM algorithm based on a user labeled real trajectory dataset. As a result, the IVMM algorithm outperforms the related method (ST-Matching algorithm). <s> BIB014 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> This paper presents a smart driving direction system leveraging the intelligence of experienced drivers. In this system, GPS-equipped taxis are employed as mobile sensors probing the traffic rhythm of a city and taxi drivers' intelligence in choosing driving directions in the physical world. We propose a time-dependent landmark graph to model the dynamic traffic pattern as well as the intelligence of experienced drivers so as to provide a user with the practically fastest route to a given destination at a given departure time. Then, a Variance-Entropy-Based Clustering approach is devised to estimate the distribution of travel time between two landmarks in different time slots. Based on this graph, we design a two-stage routing algorithm to compute the practically fastest and customized route for end users. We build our system based on a real-world trajectory data set generated by over 33,000 taxis in a period of three months, and evaluate the system by conducting both synthetic experiments and in-the-field evaluations. As a result, 60-70 percent of the routes suggested by our method are faster than the competing methods, and 20 percent of the routes share the same results. On average, 50 percent of our routes are at least 20 percent faster than the competing approaches. <s> BIB015 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> The advances in location-acquisition and mobile computing techniques have generated massive spatial trajectory data, which represent the mobility of a diversity of moving objects, such as people, vehicles, and animals. Many techniques have been proposed for processing, managing, and mining trajectory data in the past decade, fostering a broad range of applications. In this article, we conduct a systematic survey on the major research into trajectory data mining, providing a panorama of the field as well as the scope of its research topics. Following a road map from the derivation of trajectory data, to trajectory data preprocessing, to trajectory data management, and to a variety of mining tasks (such as trajectory pattern mining, outlier detection, and trajectory classification), the survey explores the connections, correlations, and differences among these existing techniques. This survey also introduces the methods that transform trajectories into other data formats, such as graphs, matrices, and tensors, to which more data mining and machine learning techniques can be applied. Finally, some public trajectory datasets are presented. This survey can help shape the field of trajectory data mining, providing a quick understanding of this field to the community. <s> BIB016 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Human mobility prediction is an important problem that has a large number of applications, especially in context-aware services. This paper presents a study on location prediction using smartphone data, in which we address modeling and application aspects. Building personalized location prediction models from smartphone data remains a technical challenge due to data sparsity, which comes from the complexity of human behavior and the typically limited amount of data available for individual users. To address this problem, we propose an approach based on kernel density estimation, a popular smoothing technique for sparse data. Our approach contributes to existing work in two ways. First, our proposed model can estimate the probability that a user will be at a given location at a specific time in the future, by using both spatial and temporal information via multiple kernel functions. Second, we also show how our probabilistic framework extends to a more practical task of location prediction for a time window in the future. Our approach is validated on an everyday life location dataset consisting of 133 smartphone users. Our method reaches an accuracy of 84% for the next hour, and an accuracy of 77% for the next three hours. <s> BIB017 </s> Urban flows prediction from spatial-temporal data using machine learning: A survey <s> Spatial-temporal data for urban flows prediction <s> Large volumes of spatio-temporal data are increasingly collected and studied in diverse domains, including climate science, social sciences, neuroscience, epidemiology, transportation, mobile health, and Earth sciences. Spatio-temporal data differ from relational data for which computational approaches are developed in the data-mining community for multiple decades in that both spatial and temporal attributes are available in addition to the actual measurements/attributes. The presence of these attributes introduces additional challenges that needs to be dealt with. Approaches for mining spatio-temporal data have been studied for over a decade in the data-mining community. In this article, we present a broad survey of this relatively young field of spatio-temporal data mining. We discuss different types of spatio-temporal data and the relevant data-mining questions that arise in the context of analyzing each of these datasets. Based on the nature of the data-mining problem studied, we classify literature on spatio-temporal data mining into six major categories: clustering, predictive learning, change detection, frequent pattern mining, anomaly detection, and relationship mining. We discuss the various forms of spatio-temporal data-mining problems in each of these categories. <s> BIB018
In this section, we choose the spatial-temporal dynamic data (trajectories data) as a case study for the urban flows prediction task because it as one of widely studied spatial-temporal data types in urban flows forecasting and it relates more with our urban crowd flows and traffic flows prediction topic. In the spatial-temporal data mining field, spatial-temporal (ST) data types can be divided into four categories BIB018 , which are different from the classification we mentioned in Table 1 above: (i) event data, which often occur at point locations and times (e.g., a concert or a car accident), (ii) trajectory data, which refer to the trajectories of moving objects (e.g., human, vehicle, animals), (iii) point reference data, where a continuous spatial-temporal field is being measured at moving ST reference sites (e.g., surface temperature are measured by using weather balloons), and (iv) raster data, whose measurements of an ST field are collected at fixed ST grids (e.g., air quality of Earth's surface collected by ground-based sensors). We can find that the ST events data and ST point reference data are point data, while trajectories data and ST raster data are network data. They can be merged into the categories of spatial-temporal datasets showed in Table 1 . As we know, the derivation of trajectories data can be classified into four main categories, which are human mobility, transportation vehicles mobility, animals mobility and natural phenomena BIB016 . In this paper, the urban flows prediction task mainly aim at estimated and predict human mobility and transportation vehicles mobility. Before starting data mining tasks for urban flows prediction, we should preprocess these spatial-temporary dynamic trajectory data. The raw location traces are often collected by smartphones with GPS and WiFi or taxis equipped with a GPS sensor. There are some spatial-temporal trajectory data preprocessing methods, consisting of extracting the history of place visits, data filtering and statistics, trajectory compression, trajectory segmentation and map matching BIB016 BIB017 . Extracting the history of place visits. From the analysis of the location traces, we can find that there are transitions and stay points in trajectories data. Then using a gird clustering algorithm BIB017 , the stay regions will be generated from the set of stay points based on a given radius. So the history of place that users visited can be extracted. As demonstrated in Figure 2 , if we set the minimum time of stay points to 5 min, the bus station (P4) can be found in this trajectory, and the stay region can be generated around the school (P9) about 1km radius. Based on these places with timestamp information, some applications may appear, such as travel recommendation, business location and travel time estimation. Data filtering and statistics. Because of sensor's error or other technical issues, there are some incomplete instances or outliers in the trajectories data. To forecast urban flows well, we need to filter out these incomplete instances and outliers before prediction task. The filter step is significant to avoid biased estimates of prediction performance. In order to find the trajectories distribution, we also need to perform some statistics analysis, such as mean, median, the ratio between location and transitions, and how many places visited by a user during a given recording interval. Trajectory compression. Let's imagine this condition. We can collect time-stamped location every second even more accurate time measurements for moving objects. It will cost plenty of communication, computing and storage sources. To efficiently collected and leverage these data, we need to compress the trajectory data. There are two major categories of trajectory compression methods. One is offline compression, such as Douglas-Peucker algorithm BIB001 which replaces the original trajectory by an approximate line segment until the negligible error is below a specified error. The other is online compression, such as Sliding Window algorithm BIB002 and Open Window algorithm BIB005 to transmit trajectory data timely. They are window-based algorithms which fit the trajectory points in a sliding window with a valid line segment and expand the sliding window until exceed specified error bound. Trajectory segmentation. In order to classify or cluster trajectories to mine more useful knowledge, we need to study trajectory segmentation before mining tasks. There are three common types of trajectory segmentation methods. They are time interval-based, shape of a trajectory-based and semantic meaning-based methods. The first one is that a trajectory is divided into some segments based on a given time-length (lager than the given threshold or the same time interval), as illustrated in Figure 3 . Due to the time length between p2 and p3 being larger than a given time interval, so we can divide the trajectory into two segments (p1p2 and p3p7). The second one is that we can partition a trajectory by the turning points with heading direction changing over a threshold BIB016 . The last one is based on the semantic meaning of points in a trajectory. For example, in the travel speed estimation task, we often remove the stay points from the GPS trajectories because the stay points may be location where taxi is waiting for passengers BIB015 . For example, from Figure 3 , the trajectory points in the dotted box can be removed because of stay points (p4p5p6) and the trajectory can be divided into two segments (p1p3 and p6p7). To find a walk-based segmentation BIB013 BIB009 , we also need to combine with the human mobility patterns and employ further semantic meaning-based trajectory segmentation research. Map matching. There are two major categories map matching methods. One is the additional information-base method, and the other is the range of sampling points-based method. The first type of methods can be divided into four groups: geometric BIB003 , topological  BIB006 , probabilistic BIB008 BIB010 and other advanced methods BIB011 BIB014 BIB012 . The second type of methods can be divided into two categories: local and global methods. The local methods aim to find a local optimal point based on the distance and orientation similarity. The global methods BIB004 BIB007 try to match an entire trajectory with a road network.