Evaluating Local Non-Stationarity when Considering the Spatial Variation of Large-scale Autocorrelation

Multi‐scale effects of spatial autocorrelation may be present in datasets. Given the importance of detecting local non‐stationarity in many theoretical as well as applied studies, it is necessary to “remove” the impact of large‐scale autocorrelation before common techniques for local pattern analysis are applied. It is proposed in this paper to employ the regionalized range to define spatially varying sub‐regions within which the impact of large‐scale autocorrelation is minimized and the local patterns can be investigated. A case study is conducted on crime data to detect crime hot spots and cold spots in San Antonio, Texas. The results confirm the necessity of treating the non‐stationarity of large‐scale spatial autocorrelation prior to any action aiming at detecting local autocorrelation.     

A spatial‐knowledge‐enhanced heuristic for solving the p‐median problem

The p‐median problem (PMP) is one of the most applied location problems in urban and regional planning. As an NP‐hard problem, the PMP remains challenging to solve optimally, especially for large‐sized problems. A number of heuristics have been developed to obtain PMP solutions in a fast manner. Among the heuristics, the Teitz and Bart (TB) algorithm has been found effective for finding high‐quality solutions. In this article, we present a spatial‐knowledge‐enhanced Teitz and Bart (STB) heuristic method for solving PMPs. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and service provision. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. This new algorithm can be incorporated into current commercial GIS packages to solve a wide range of location‐allocation problems.     

Grid-enabling Geographically Weighted Regression: A Case Study of Participation in Higher Education in England

Geographically Weighted Regression (GWR) is a method of spatial statistical analysis used to explore geographical differences in the effect of one or more predictor variables upon a response variable. However, as a form of local analysis, it does not scale well to (especially) large data sets because of the repeated processes of fitting and then comparing multiple regression surfaces. A solution is to make use of developing grid infrastructures, such as that provided by the National Grid Service (NGS) in the UK, treating GWR as an "embarrassing parallel" problem and building on existing software platforms to provide a bridge between an open source implementation of GWR (in R) and the grid system. To demonstrate the approach, we apply it to a case study of participation in Higher Education, using GWR to detect spatial variation in social, cultural and demographic indicators of participation.     

A Parallel Scheme for Large‐scale Polygon Rasterization on CUDA‐enabled GPUs

This research develops a parallel scheme to adopt multiple graphics processing units (GPUs) to accelerate large‐scale polygon rasterization. Three new parallel strategies are proposed. First, a decomposition strategy considering the calculation complexity of polygons and limited GPU memory is developed to achieve balanced workloads among multiple GPUs. Second, a parallel CPU/GPU scheduling strategy is proposed to conceal the data read/write times. The CPU is engaged with data reads/writes while the GPU rasterizes the polygons in parallel. This strategy can save considerable time spent in reading and writing, further improving the parallel efficiency. Third, a strategy for utilizing the GPU's internal memory and cache is proposed to reduce the time required to access the data. The parallel boundary algebra filling (BAF) algorithm is implemented using the programming models of compute unified device architecture (CUDA), message passing interface (MPI), and open multi‐processing (OpenMP). Experimental results confirm that the implemented parallel algorithm delivers apparent acceleration when a massive dataset is addressed (50.32 GB with approximately 1.3 × 10⁸ polygons), reducing conversion time from 25.43 to 0.69 h, and obtaining a speedup ratio of 36.91. The proposed parallel strategies outperform the conventional method and can be effectively extended to a CPU‐based environment.     

交通网络旅行商路径优化的遗传禁忌搜索算法

旅行商路径优化问题是经典的网络分析问题之一。由于旅行商问题具有NP Hard特性,主要通过智能优化方法或启发式算法来获得近似最优解。然而,单一智能优化方法存在运算量过大、参数选择苛刻,对初值依赖性强等缺陷,很难快速实现全局优化。结合多种优化机制和邻域搜索结构设计混合启发式算法可在一定程度上解决这一问题。本文结合遗传算法的全局寻优能力和禁忌搜索的记忆功能,设计实现了一种基于分散集中策略的禁忌遗传算法,即采用遗传变异算子作为分散策略构造邻域,开辟新的搜索空间,有效提升获得全局最优解的概率;将禁忌搜索作为集中策略进行局部寻优,避免迂回探测,充分体现禁忌搜索较强的“爬山”能力,并通过实际交通网络和不同规模的节点集合,从求解精度、稳定性和效率三个方面对算法进行了评价。结果表明,本文提出的交通网络旅行商路径优化的禁忌遗传算法平均求解精度比禁忌搜索算法提高了9%,略优于ArcGIS;当与ArcGIS求解的TSP路径长度差异在1%以内时,禁忌搜索算法已经难以获得对应精度的TSP路径,而禁忌遗传算法效率比遗传算法提高了50%。且禁忌遗传算法具有很好的并行化潜力。     

Improving Geocode Accuracy with Candidate Selection Criteria

Geocoding systems typically use more than one geographic reference dataset to improve match rates and spatial accuracy, resulting in multiple candidate geocodes from which the single “best” result must be selected. Little scientific evidence exists for formalizing this selection process or comparing one strategy to another, leading to the approach used in existing systems which we term the hierarchy‐based criterion: place the available reference data layers into qualitative, static, and in many cases, arbitrary hierarchies and attempt a match in each layer, in order. The first non‐ambiguous match with suitable confidence is selected and returned as output. This approach assumes global relationships of relative accuracy between reference data layers, ignoring local variations that could be exploited to return more precise geocodes. We propose a formalization of the selection criteria and present three alternative strategies which we term the uncertainty‐, gravitationally‐, and topologically‐based strategies. The performance of each method is evaluated against two ground truth datasets of nationwide GPS points to determine any resulting spatial improvements. We find that any of the three new methods improves on current practice in the majority of cases. The gravitationally‐ and topologically‐based approaches offer improvement over a simple uncertainty‐based approach in cases with specific characteristics.     

An efficient data organization and scheduling strategy for accelerating large vector data rendering

Rendering large volumes of vector data is computationally intensive and therefore time consuming, leading to lower efficiency and poorer interactive experience. Graphics processing units (GPUs) are powerful tools in data parallel processing but lie idle most of the time. In this study, we propose an approach to improve the performance of vector data rendering by using the parallel computing capability of many‐core GPUs. Vertex transformation, largely a mathematical calculation that does not require communication with the host storage device, is a time‐consuming procedure because all coordinates of each vector feature need to be transformed to screen vertices. Use of a GPU enables optimization of a general‐purpose mathematical calculation, enabling the procedure to be executed in parallel on a many‐core GPU and optimized effectively. This study mainly focuses on: (1) an organization and storage strategy for vector data based on equal pitch alignment, which can adapt to the GPU's calculating characteristics; (2) a paging‐coalescing transfer and memory access strategy for vector data between the CPU and the GPU; and (3) a balancing allocation strategy to take full advantage of all processing cores of the GPU. Experimental results demonstrate that the approach proposed can significantly improve the efficiency of vector data rendering.     

A local approach to optimize the scale parameter in multiresolution segmentation for multispectral imagery

The results obtained using the object-based image analysis approach for remote sensing image analysis depend strongly on the quality of the segmentation step. In this paper, to optimize the scale parameter in a multiresolution segmentation, we analyse a high-resolution image of a large and heterogeneous agricultural area. This approach is based on using a set of agricultural plots extracted from official maps as uniform spatial units. The scale parameter is then optimized in each uniform spatial unit. Intra-object and inter-object heterogeneity measurements are used to evaluate each segmentation. To avoid subsegmentation, some oversegmentation is allowed, but is attenuated in a second step using the spectral difference segmentation algorithm. The statistical distribution of the scale parameter is not equal in all land uses, indicating the soundness of this local approach. A quantitative assessment of the results was also conducted for the different land covers. The results indicate that the spectral contrast between objects is larger with the local approach than with the global approach. These differences were statistically significant in all land uses except irrigated fruit trees and greenhouses. In the absence of subsegmentation, this suggests that the objects will be placed far apart in the space of variables, even if they are very close in the physical space. This is an obvious advantage in a subsequent classification of the objects.     

A spatial‐temporal‐semantic approach for detecting local events using geo‐social media data

Social media networks allow users to post what they are involved in with location information in a real‐time manner. It is therefore possible to collect large amounts of information related to local events from existing social networks. Mining this abundant information can feed users and organizations with situational awareness to make responsive plans for ongoing events. Despite the fact that a number of studies have been conducted to detect local events using social media data, the event content is not efficiently summarized and/or the correlation between abnormal neighboring regions is not investigated. This article presents a spatial‐temporal‐semantic approach to local event detection using geo‐social media data. Geographical regularities are first measured to extract spatio‐temporal outliers, of which the corresponding tweet content is automatically summarized using the topic modeling method. The correlation between outliers is subsequently examined by investigating their spatial adjacency and semantic similarity. A case study on the 2014 Toronto International Film Festival (TIFF) is conducted using Twitter data to evaluate our approach. This reveals that up to 87% of the events detected are correctly identified compared with the official TIFF schedule. This work is beneficial for authorities to keep track of urban dynamics and helps build smart cities by providing new ways of detecting what is happening in them.     

Incorporating sprawl and adjacency measures in land‐use forecasting model: A case study of Collin County,TX

Sprawl measures have largely been neglected in land‐use forecasting models. The current approach for land‐use allocation using optimization mostly utilizes objective functions and constraints that are non‐spatial in nature. Application of spatial constraints could take care of the contiguity and compactness of land uses and can be utilized to address urban sprawl. Because a land‐use model is used as an input to transportation modeling, a better spatial allocation strategy for more compact land‐use projections will promote better transportation planning and sustainable development. This study formulates a scenario‐based approach to normative modeling of urban sprawl. In doing so, it seeks to improve the land‐use projections by employing a spatial optimization model with contiguity and compactness consideration. This study incorporates urban sprawl measures based on smart growth principles together with a mixed‐use factor, and adjacency consideration of nearby land uses. The objective function used in the study maximizes net suitability based on imposed constraints. These constraints are based on smart growth principles that enhance walkability in neighborhoods, promote better health for residents, and encourage mixed‐use development. The formulated model has been applied to Collin County, TX, a fast‐developing suburban county located to the north of the Dallas–Fort Worth metroplex. The suitability of land cells indicates the probability of conversion, which is calculated using spatial discrete choice analysis with Moran eigenvector spatial filtering for vacant cells at a resolution of 150 × 150 m employing factors of the built environment, and socioeconomic and demographic characteristics. This study demonstrates how spatial proximity between land uses, which has been ignored to date, can be used to control sprawl, resulting in better mixing of different land uses based on constraints imposed in a spatial optimization problem.     

Spatial‐Scene Similarity Queries

Assessing spatial scenes for similarity is difficult from a cognitive and computational perspective. Solutions to spatial‐scene similarity assessments are sensible only if corresponding elements in the compared scenes are identified correctly. This matching process becomes increasingly complex and error‐prone for large spatial scenes as it is questionable how to choose one set of associations over another or how to account quantitatively for unmatched elements. We develop a comprehensive methodology for similarity queries over spatial scenes that incorporates cognitively motivated approaches about scene comparisons, together with explicit domain knowledge about spatial objects and their relations for the relaxation of spatial query constraints. Along with a sound graph‐theoretical methodology, this approach provides the foundation for plausible reasoning about spatial‐scene similarity queries.     

A Dynamic Network with Individual Mobility for Designing Vaccination Strategies

Vaccination is a primary means to control infectious diseases. Few studies on vaccination strategies have explicitly considered the mobility of individuals. This article aims to evaluate the efficacy of three vaccination strategies in a dynamic social network, in which individuals are mobile between and within communities. The three vaccination strategies are applied to this social network for evaluation, including a travel‐based, a contact‐based, and a random vaccination strategy. Simulation results show that the contact‐based strategy, commonly seen in previous studies, is not always the most effective strategy in dynamic networks. This strategy is preferable for a population with a large number of intercommunity travelers, for instance in urban areas. On the other hand, the travel‐based strategy, although directly accounting for individual mobility, is not necessarily the most effective in dynamic networks either. This strategy is recommended for a population with a small number of intercommunity travelers, such as rural areas. In addition, one advantage of the travel‐based strategy over the other two is its efficacy in confining the spatial extent of affected areas. Results suggest that the intercommunity travel of individuals should be a major consideration for choosing proper vaccination strategies. By adding the spatial context into vaccination strategies, this research provides new insights into community‐based planning for infectious disease control.     

PC集群环境下的并行地理网络车辆路径算法

针对PC集群计算节点内存小、进程间通信速度慢的问题,本文设计了分布式的数据存储机制;提出了用同步变换规则代替解编码传输的进程间通信方式;基于邻域分解策略实现了禁忌搜索过程的并行化,发展了一种适用于PC集群环境的并行地理网络VRP算法。应用模拟路网数据进行了相关试验,结果表明：本文算法的计算结果与ArcGIS基本一致,二者平均偏差率在2.11%~2.87%之间;分布式数据存储策略有效地降低了各进程对内存的需求量,保证了算法的稳健性和扩展性;通过算法的并行化提高了VRP算法的求解效率;该算法具有良好的加速性能,8进程时在各测试数据集中的加速比均在4.46~6.32之间。     

A Spatio‐Temporal Graph Model for Marine Dune Dynamics Analysis and Representation

Defining a model for the representation and the analysis of spatio‐temporal dynamics remains an open domain in geographical information sciences. In this article we investigate a spatio‐temporal graph‐based model dedicated to managing and extracting sets of geographical entities related in space and time. The approach is based on spatial and temporal local relations between neighboring entities during consecutive times. The model allows us to extract sets of connected entities distant in time and space over long periods and large spaces. From GIS concepts and qualitative reasoning on space and time, we combine the graph model with a dedicated spatial database. It includes information on geometry and geomorphometric parameters, and on spatial and temporal relations. This allows us to extend classical measurements of spatial parameters, with comparisons of entities linked by complex relations in space and time. As a case study, we show how the model suggests an efficient representation of dunes dynamics on a nautical chart for safe navigation.     

An Adaptive Method of Non‐stationary Variogram Modeling for DEM Error Surface Simulation

Geostatistical characterization of local DEM error is usually based on the assumption of a stationary variogram model which requires the mean and variance to be finite and constant in the area under investigation. However, in practice this assumption is appropriate only in a restricted spatial location, where the local experimental variograms vary slowly. Therefore, an adaptive method is developed in this article to model non‐stationary variograms, for which the estimator and the indicator for characterization of spatial variation are a Voronoi map and the standard deviation of mean values displayed in the Voronoi map, respectively. For the adaptive method, the global domain is divided into different meshes with various sizes according to the variability of local variograms. The adaptive method of non‐stationary variogram modeling is applied to simulating error surfaces of a LiDAR derived DEM located in Sichuan province, China. Results indicate that the locally adaptive variogram model is more accurate than the global one for capturing the characterization of spatial variation in DEM errors. The adaptive model can be considered as an alternative approach to modeling non‐stationary variograms for DEM error surface simulation.     

Multi‐Scale Qualitative Location: A Topology‐Based Model

Qualitative locations describe spatial objects by relating the spatial objects to a frame of reference (e.g. a regional partition in this study) with qualitative relations. Existing models only formalize spatial objects, frames of reference, and their relations at one scale, thus limiting their applicability in representing location changes of spatial objects across scales. A topology‐based, multi‐scale qualitative location model is proposed to represent the associations of multiple representations of the same objects with respect to the frames of reference at different levels. Multi‐scale regional partitions are first presented to be the frames of reference at multiple levels of scale. Multi‐scale locations are then formalized to relate multiple representations of the same objects to the multiple frames of reference by topological relations. Since spatial objects, frames of reference, and topological relations in qualitative locations are scale dependent, scale transformation approaches are presented to derive possible coarse locations from detailed locations by incorporating polygon merging, polygon‐to‐line and polygon‐to‐point operators.     

Spatial optimization for land acquisition problems: A review of models,solution methods,and GIS support

This article reviews the interdisciplinary research field of spatial optimization for land acquisition problems. We start with a theoretical framework to identify three categories of spatial optimization models: problems with aspatial constraints, location models, and problems with topological constraints. Exact, heuristic, and metaheuristic approaches to solving these problems are critically discussed. Tools that are available in commercial and open‐source GIS packages are reviewed from four aspects. We first survey the off‐the‐shelf support and then the development environments in these packages. A case study of the one‐center problem is used to illustrate the computational performance of different solution methods. Finally the advantages and disadvantages of current GIS data models are discussed. The article concludes with challenges and future directions for solving spatial optimization problems for land acquisition.     

一种改进的基于最小生成树的遥感影像多尺度分割方法

影像分割是遥感影像面向对象信息提取的基础步骤。基于多特征、多尺度及考虑空间关系的遥感图像分割是主流研究方向。本文基于eCognition软件的多尺度分割思想,引入基于图论的最优化理论,提出了基于最小生成树分割和最小异质性准则的多尺度分割方法。该方法采用相干增强各向异性扩散滤波和最小生成树分割得到初始分割结果,通过最小异质性合并准则同时考虑多波段光谱特性区域形状参数进行区域合并,实现多尺度的影像分割。本次研究选取两景试验影像,对本文方法和eCognition软件的多尺度分割方法开展了目视比较和定量指标评价,结果表明,本文提出的方法是一种有效的影像分割方法,在光谱差异较小区域的细分方面优于eCognition方法。     

Multi‐scale approach to mining significant spatial co‐location patterns

Spatial co‐location pattern mining aims to discover a collection of Boolean spatial features, which are frequently located in close geographic proximity to each other. Existing methods for identifying spatial co‐location patterns usually require users to specify two thresholds, i.e. the prevalence threshold for measuring the prevalence of candidate co‐location patterns and distance threshold to search the spatial co‐location patterns. However, these two thresholds are difficult to determine in practice, and improper thresholds may lead to the misidentification of useful patterns and the incorrect reporting of meaningless patterns. The multi‐scale approach proposed in this study overcomes this limitation. Initially, the prevalence of candidate co‐location patterns is measured statistically by using a significance test, and a non‐parametric model is developed to construct the null distribution of features with the consideration of spatial auto‐correlation. Next, the spatial co‐location patterns are explored at multi‐scales instead of single scale (or distance threshold) discovery. The validity of the co‐location patterns is evaluated based on the concept of lifetime. Experiments on both synthetic and ecological datasets show that spatial co‐location patterns are discovered correctly and completely by using the proposed method; on the other hand, the subjectivity in discovery of spatial co‐location patterns is reduced significantly.