Movement similarity assessment using symbolic representation of trajectories

This article describes a novel approach for finding similar trajectories, using trajectory segmentation based on movement parameters (MPs) such as speed, acceleration, or direction. First, a segmentation technique is applied to decompose trajectories into a set of segments with homogeneous characteristics with respect to a particular MP. Each segment is assigned to a movement parameter class (MPC), representing the behavior of the MP. Accordingly, the segmentation procedure transforms a trajectory to a sequence of class labels, that is, a symbolic representation. A modified version of edit distance called normalized weighted edit distance (NWED) is introduced as a similarity measure between different sequences. As an application, we demonstrate how the method can be employed to cluster trajectories. The performance of the approach is assessed in two case studies using real movement datasets from two different application domains, namely, North Atlantic Hurricane trajectories and GPS tracks of couriers in London. Three different experiments have been conducted that respond to different facets of the proposed techniques and that compare our NWED measure to a related method.     

Visual analytics of delays and interaction in movement data

The analysis of interaction between movement trajectories is of interest for various domains when movement of multiple objects is concerned. Interaction often includes a delayed response, making it difficult to detect interaction with current methods that compare movement at specific time intervals. We propose analyses and visualizations, on a local and global scale, of delayed movement responses, where an action is followed by a reaction over time, on trajectories recorded simultaneously. We developed a novel approach to compute the global delay in subquadratic time using a fast Fourier transform (FFT). Central to our local analysis of delays is the computation of a matching between the trajectories in a so-called delay space. It encodes the similarities between all pairs of points of the trajectories. In the visualization, the edges of the matching are bundled into patches, such that shape and color of a patch help to encode changes in an interaction pattern. To evaluate our approach experimentally, we have implemented it as a prototype visual analytics tool and have applied the tool on three bidimensional data sets. For this we used various measures to compute the delay space, including the directional distance, a new similarity measure, which captures more complex interactions by combining directional and spatial characteristics. We compare matchings of various methods computing similarity between trajectories. We also compare various procedures to compute the matching in the delay space, specifically the Fréchet distance, dynamic time warping (DTW), and edit distance (ED). Finally, we demonstrate how to validate the consistency of pairwise matchings by computing matchings between more than two trajectories.     

Ecological metrics and methods for GPS movement data

The growing field of movement ecology uses high resolution movement data to analyze animal behavior across multiple scales: from individual foraging decisions to population-level space-use patterns. These analyses contribute to various subfields of ecology – inter alia behavioral, disease, landscape, resource, and wildlife – and facilitate novel exploration in fields ranging from conservation planning to public health. Despite the growing availability and general accessibility of animal movement data, much potential remains for the analytical methods of movement ecology to be incorporated in all types of geographic analyses. This review provides for the Geographical Information Sciences (GIS) community an overview of the most common movement metrics and methods of analysis employed by animal ecologists. Through illustrative applications, we emphasize the potential for movement analyses to promote transdisciplinary GIS/wildlife-ecology research.     

Robust inferences of travel paths from GPS trajectories

Monitoring and predicting traffic conditions are of utmost importance in reacting to emergency events in time and for computing the real-time shortest travel-time path. Mobile sensors, such as GPS devices and smartphones, are useful for monitoring urban traffic due to their large coverage area and ease of deployment. Many researchers have employed such sensed data to model and predict traffic conditions. To do so, we first have to address the problem of associating GPS trajectories with the road network in a robust manner. Existing methods rely on point-by-point matching to map individual GPS points to a road segment. However, GPS data is imprecise due to noise in GPS signals. GPS coordinates can have errors of several meters and, therefore, direct mapping of individual points is error prone. Acknowledging that every GPS point is potentially noisy, we propose a radically different approach to overcome inaccuracy in GPS data. Instead of focusing on a point-by-point approach, our proposed method considers the set of relevant GPS points in a trajectory that can be mapped together to a road segment. This clustering approach gives us a macroscopic view of the GPS trajectories even under very noisy conditions. Our method clusters points based on the direction of movement as a spatial-linear cluster, ranks the possible route segments in the graph for each group, and searches for the best combination of segments as the overall path for the given set of GPS points. Through extensive experiments on both synthetic and real datasets, we demonstrate that, even with highly noisy GPS measurements, our proposed algorithm outperforms state-of-the-art methods in terms of both accuracy and computational cost.     

From A to B,randomly: a point-to-point random trajectory generator for animal movement

For applications in animal movement, we propose a random trajectory generator (RTG) algorithm that combines the concepts of random walks, space-time prisms, and the Brownian bridge movement model and is capable of efficiently generating random trajectories between a given origin and a destination point, with the least directional bias possible. Since we provide both a planar and a spherical version of the algorithm, it is suitable for simulating trajectories ranging from the local scale up to the (inter-)continental scale, as exemplified by the movement of migrating birds. The algorithm accounts for physical limitations, including maximum speed and maximum movement time, and provides the user with either single or multiple trajectories as a result. Single trajectories generated by the RTG algorithm can be used as a null model to test hypotheses about movement stimuli, while the multiple trajectories can be used to create a probability density surface akin to Brownian bridges.     

Unveiling movement uncertainty for robust trajectory similarity analysis

Trajectory data analysis and mining require distance and similarity measures, and the quality of their results is directly related to those measures. Several similarity measures originally proposed for time-series were adapted to work with trajectory data, but these approaches were developed for well-behaved data that usually do not have the uncertainty and heterogeneity introduced by the sampling process to obtain trajectories. More recently, similarity measures were proposed specifically for trajectory data, but they rely on simplistic movement uncertainty representations, such as linear interpolation. In this article, we propose a new distance function, and a new similarity measure that uses an elliptical representation of trajectories, being more robust to the movement uncertainty caused by the sampling rate and the heterogeneity of this kind of data. Experiments using real data show that our proposal is more accurate and robust than related work.     

三角平面拟合法在GPS高程测量中的应用

本文介绍了"三角平面拟合法"在GPS高程测量中的应用,该方法应用三角平面拟合法通过控制点的高程异常数据直接内插求得待测点的高程异常,从而求得待测点的海拔高程即正常高。较高精度地改正了GPS在测量海拔高程时的系统误差。     

A temporal-contextual analysis of urban dynamics using location-based data

The dynamics of urban activities in Jerusalem were studied by analyzing a large-scale semantically rich movement dataset. The semantic enrichment process was based on coupling movement trajectories sampled by GPS loggers with contextual data derived from trajectory-based digital activity dairies. Although the utility of such procedures in generating trajectory-specific semantic data was noted before, their application stays limited. In this paper, we promote the utilization of these procedures by demonstrating that they are not only feasible but also important for mobility studies. We discuss the characteristics of the semantic enrichment process and the manner by which it was applied within the large-scale analysis of urban dynamics. This application uncovered a time- and context-dependent array of centers in Jerusalem, resulting in a semantically rich characterization of urban dynamics. Such characterization provides otherwise unobtainable insights crucial for urban analysis. Wider implications for movement studies may be derived, as this application demonstrates how diary-based enrichment approaches hold the potential to advance bridging the semantic gap in mobility research.     

On the use of dimensioned measures of error to evaluate the performance of spatial interpolators

Spatial cross‐validation and average‐error statistics are examined with respect to their abilities to evaluate alternate spatial interpolation methods. A simple cross‐validation methodology is described, and the relative abilities of three, dimensioned error statistics—the root‐mean‐square error (RMSE), the mean absolute error (MAE), and the mean bias error (MBE)—to describe average interpolator performance are examined. To illustrate our points, climatologically averaged weather‐station temperatures were obtained from the Global Historical Climatology Network (GHCN), Version 2, and then alternately interpolated spatially (gridded) using two spatial‐interpolation procedures. Substantial differences in the performance of our two spatial interpolators are evident in maps of the cross‐validation error fields, in the average‐error statistics, as well as in estimated land‐surface‐average air temperatures that differ by more than 2°C. The RMSE and its square, the mean‐square error (MSE), are of particular interest, because they are the most widely reported average‐error measures, and they tend to be misleading. It (RMSE) is an inappropriate measure of average error because it is a function of three characteristics of a set of errors, rather than of one (the average error). Our findings indicate that MAE and MBE are natural measures of average error and that (unlike RMSE) they are unambiguous.     

西南极菲尔德斯GPS形变网监测数据的误差特性分析与处理

本文对西南极菲尔德斯形变网ＧＰＳ监测数据的误差特性进行分析，利用数理统计原理检验了数据中的系统误差，提出了削弱这类系统误差的方法。该方法有３个特点：１．以监测网中两个稳定点为基准；２．对监测网数据进行尺度因子改正与坐标变换迭代计算；３．归算后监测网点位结构不变。经改化处理后的数据，基本上消除了系统误差的影响。     

High-Resolution Measurement and Analysis of Visitor Experiences in Time and Space: The Case of Aalborg Zoo in Denmark

The notion of consumer and user experience has become dominant in our society in recent years, especially in relation to leisure activities. In this study we used the experience sampling method (ESM) data collection technique in Aalborg Zoo, Denmark, to understand the distribution of subjective experiences within this site. Visitors to the zoo were asked to send phone messages (SMS) about their subjective feelings in real time and to carry with them Global Positioning System (GPS) devices that recorded their movement. This method allowed us to geotag experiences of visitors throughout the zoo compound. The results indicate that the quality of experience of visitors varies both in time and in space. We conclude that there is a need to further explore the effect of place on experiences using repeat, high-resolution measurements. In this regard we believe that geographers, who have a long tradition of studying human–environment relations, have the tools to lead this type of exploration.     

Spatial autocorrelation and data uncertainty in the American Community Survey: a critique

ABSTRACT

We argue that the use of American Community Survey (ACS) data in spatial autocorrelation statistics without considering error margins is critically problematic. Public health and geographical research has been slow to recognize high data uncertainty of ACS estimates, even though ACS data are widely accepted data sources in neighborhood health studies and health policies. Detecting spatial autocorrelation patterns of health indicators on ACS data can be distorted to the point that scholars may have difficulty in perceiving the true pattern. We examine the statistical properties of spatial autocorrelation statistics of areal incidence rates based on ACS data. In a case study of teen birth rates in Mecklenburg County, North Carolina, in 2010, Global and Local Moran’s I statistics estimated on 5-year ACS estimates (2006–2010) are compared to ground truth rate estimates on actual counts of births certificate records and decennial-census data (2010). Detected spatial autocorrelation patterns are found to be significantly different between the two data sources so that actual spatial structures are misrepresented. We warn of the possibility of misjudgment of the reality and of policy failure and argue for new spatially explicit methods that mitigate the biasedness of statistical estimations imposed by the uncertainty of ACS data.     

Bias estimation and correction for triangle-based surface area calculations

The calculation of surface area is meaningful for a variety of space-filling phenomena, e.g., the packing of plants or animals within an area of land. With Digital Elevation Model (DEM) data we can calculate the surface area by using a continuous surface model, such as by the Triangulated Irregular Network (TIN). However, just as the triangle-based surface area discussed in this paper, the surface area is generally biased because it is a nonlinear mapping about the DEM data which contain measurement errors. To reduce the bias in the surface area, we propose a second-order bias correction by applying nonlinear error propagation to the triangle-based surface area. This process reveals that the random errors in the DEM data result in a bias in the triangle-based surface area while the systematic errors in the DEM data can be reduced by using the height differences. The bias is theoretically given by a probability integral which can be approximated by numerical approaches including the numerical integral and the Monte Carlo method; but these approaches need a theoretical distribution assumption about the DEM measurement errors, and have a very high computational cost. In most cases, we only have variance information on the measurement errors; thus, a bias estimation based on nonlinear error propagation is proposed. Based on the second-order bias estimation proposed, the variance of the surface area can be improved immediately by removing the bias from the original variance estimation. The main results are verified by the Monte Carlo method and by the numerical integral. They show that an unbiased surface area can be obtained by removing the proposed bias estimation from the triangle-based surface area originally calculated from the DEM data.     

An ensemble approach to space–time interpolation

The availability of spatial data on an unprecedented scale as well as advancements in analytical and visualization techniques gives researchers the opportunity to study complex problems over large urban and regional areas. Nevertheless, few individual data sets exist that provide both the requisite spatial and/or temporal observational frequency to truly facilitate detailed investigations. Some data are collected frequently over time but only at a few geographic locations (e.g., weather stations). Similarly, other data are collected with a high level of spatial resolution but not at regular or frequent time intervals (e.g., satellite data). The purpose of this article is to present an interpolation approach that leverages the relative temporal richness of one data set with the relative spatial richness of another to fill in the gaps. Because different interpolation techniques are more appropriate than others for specific types of data, we propose a space–time interpolation approach whereby two interpolation methods – one for the temporal and one for the spatial dimension – are used in tandem to increase the accuracy results.

We call our ensemble approach the space–time interpolation environment (STIE). The primary steps within this environment include a spatial interpolation processor, a temporal interpolation processor, and a calibration processor, which enforces phenomenon-related behavioral constraints. The specific interpolation techniques used within the STIE can be chosen on the basis of suitability for the data and application at hand. In this article, we first describe STIE conceptually including the data input requirements, output structure, details of the primary steps, and the mechanism for coordinating the data within those steps. We then describe a case study focusing on urban land cover in Phoenix, Arizona, using our working implementation. Our empirical results show that our approach increased the accuracy for estimating urban land cover better than a single interpolation technique.     

Fast map matching,an algorithm integrating hidden Markov model with precomputation

Wide deployment of global positioning system (GPS) sensors has generated a large amount of data with numerous applications in transportation research. Due to the observation error, a map matching (MM) process is commonly performed to infer a path on a road network from a noisy GPS trajectory. The increasing data volume calls for the design of efficient and scalable MM algorithms. This article presents fast map matching (FMM), an algorithm integrating hidden Markov model with precomputation, and provides an open-source implementation. An upper bounded origin-destination table is precomputed to store all pairs of shortest paths within a certain length in the road network. As a benefit, repeated routing queries known as the bottleneck of MM are replaced with hash table search. Additionally, several degenerate cases and a problem of reverse movement are identified and addressed in FMM. Experiments on a large collection of real-world taxi trip trajectories demonstrate that FMM has achieved a considerable single-processor MM speed of 25,000–45,000 points/second varying with the output mode. Investigation on the running time of different steps in FMM reveals that after precomputation is employed, the new bottleneck is located in candidate search, and more specifically, the projection of a GPS point to the polyline of a road edge. Reverse movement in the result is also effectively reduced by applying a penalty.     

A Cartographic Analysis Using Spatial Filter Logistic Model Specifications for Implementing Mosquito Control in Kenya

Negative spatial autocorrelation (NSA), the tendency for dissimilar neighboring values to cluster on a map, may go undetected in statistical analyses of immature Anopheles gambiae s.l., a leading malaria mosquito vector in Sub-Saharan Africa. Unquantified NSA generated from an inverse variance-covariance matrix may generate misspecifications in an An. gambiae s.l. habitat model. In this research, we used an eigenfunction decomposition algorithm based on a modified geographic connectivity matrix to compute the Moran's I statistic, to uncover hidden NSA in a dataset of georeferenced An. gambiae s.l. habitat explanatory predictor variables spatiotemporally sampled in Malindi and Kisumu, Kenya. The Moran's I statistic was decomposed into orthogonal synthetic map patterns. Global tests revealed that |z_MC|s generated were less than 1.11 for the presence of latent autocorrelation. The algorithm captured NSA in the An. gambiae s.l. habitat data by quantifying all non-normal random variables, space-time heterogeneity, and distributional properties of the spatial filters.     

On the prediction error variance of three common spatial interpolation schemes

Three forms of linear interpolation are routinely implemented in geographical information science, by interpolating between measurements made at the endpoints of a line, the vertices of a triangle, and the vertices of a rectangle (bilinear interpolation). Assuming the linear form of interpolation to be correct, we study the propagation of error when measurement error variances and covariances are known for the samples at the vertices of these geometric objects. We derive prediction error variances associated with interpolated values at generic points in the above objects, as well as expected (average) prediction error variances over random locations in these objects. We also place all the three variants of linear interpolation mentioned above within a geostatistical framework, and illustrate that they can be seen as particular cases of Universal Kriging (UK). We demonstrate that different definitions of measurement error in UK lead to different UK variants that, for particular expected profiles or surfaces (drift models), yield weights and predictions identical with the interpolation methods considered above, but produce fundamentally different (yet equally plausible from a pure data standpoint) prediction error variances.     

Variable resolution block kriging using a hierarchical spatial data structure

Abstract

Kriging is an optimal method of spatial interpolation that produces an error for each interpolated value. Block kriging is a form of kriging that computes averaged estimates over blocks (areas or volumes) within the interpolation space. If this space is sampled sparsely, and divided into blocks of a constant size, a variable estimation error is obtained for each block, with blocks near to sample points having smaller errors than blocks farther away. An alternative strategy for sparsely sampled spaces is to vary the sizes of blocks in such away that a block's interpolated value is just sufficiently different from that of an adjacent block given the errors on both blocks. This has the advantage of increasing spatial resolution in many regions, and conversely reducing it in others where maintaining a constant size of block is unjustified (hence achieving data compression). Such a variable subdivision of space can be achieved by regular recursive decomposition using a hierarchical data structure. An implementation of this alternative strategy employing a split-and-merge algorithm operating on a hierarchical data structure is discussed. The technique is illustrated using an oceanographic example involving the interpolation of satellite sea surface temperature data. Consideration is given to the problem of error propagation when combining variable resolution interpolated fields in GIS modelling operations.     

Curvedness feature constrained map matching for low-frequency probe vehicle data

Map matching method is a fundamental preprocessing technique for massive probe vehicle data. Various transportation applications need map matching methods to provide highly accurate and stable results. However, most current map matching approaches employ elementary geometric or topological measures, which may not be sufficient to encode the characteristic of realistic driving paths, leading to inefficiency and inaccuracy, especially in complex road networks. To address these issues, this article presents a novel map matching method, based on the measure of curvedness of Global Positioning System (GPS) trajectories. The curvature integral, which measures the curvedness feature of GPS trajectories, is considered to be one of the major matching characteristics that constrain pairwise matching between the two adjacent GPS track points. In this article, we propose the definition of the curvature integral in the context of map matching, and develop a novel accurate map matching algorithm based on the curvedness feature. Using real-world probe vehicles data, we show that the curvedness feature (CURF) constrained map matching method outperforms two classical methods for accuracy and stability under complicated road environments.