Archive

  • 2015 Volume 17 Issue 5
    Published: 10 May 2015
      

  • Select all
    |
  • LIU Junzhi, ZHU Axing, QIN Chengzhi, JIANG Jingchao, ZHU Liangjun, SHEN Lin
    Download PDF ( )   Knowledge map   Save

    Watershed process simulation has become an important tool for geographical researches and decision making of watershed management. For watershed process simulation with long period, high spatial resolution and multi-process integrated modeling, the amount of required computation is so huge that the parallel computing is urgently needed to handle these simulations. Currently, the rapid development of hardware and software in parallel computing provides a good opportunity for solving the computation bottleneck of multi- process and high-resolution watershed process simulation over large regions. In order to take full advantage of the capabilities of new parallel-computing hardware, it is necessary to use geographical laws, which illustrate the characteristics of watershed processes, to guide the design and implementation of parallel computing algorithms. This paper presents that geographical laws can be used to guide the design and implementation of parallel computing algorithms for watershed process simulation from different aspects (i.e. spatial, sub-process, and temporal aspects). The laws that can be used include the spatial hierarchy structure, the interactions among spatial units, the dependences among geographical process, and the spatial-temporal dynamic of geographical processes, etc. At the end of this paper, two parallel computing cases of watershed process simulations guided by geographical laws are illustrated to show how these geographical laws can be used in real-world applications. This paper intends to provide a theoretical and methodology guidance for parallel computing of watershed process simulation and other similar types of geo-computation.

  • HE Gaojin, XIONG Wei, CHEN Luo, WU Qiuyun, JING Ning
    Download PDF ( )   Knowledge map   Save

    With the rapid development of remote sensing (RS) image acquisition and processing technology, the spatial resolution and temporal resolution of RS image have been greatly improved. For large-scale RS image, traditional sequential pyramid building algorithms have been found difficult to meet the quick browsing requirements. Technologies and facilities of high performance computing have become more and more feasible to researchers. Taking the advantages of multi-core, multi-node cluster computing environments and parallel processing mechanism is turning to be an inevitable trend. Some of recent works explore the efficiency and flexibility of parallel pyramid building methods. However, these methods all have deficiencies. For example, GPU-based parallel method is hardware-aware, the improvement of its performance is limited on a single node, and the system architecture will be too complicated when applied in a cluster environment. Whereas the distributed clusterbased method requires the data to be distributed to be stored in different nodes, and the complete pyramid file needs to be merged, which is excessive time consuming. Therefore, using the high-performance disk-shared cluster is an alternative mechanism for achieving the parallel building pyramid of large-scale RS images. In this paper, we proposed a parallel algorithm based on Message Passing Interface (MPI). Based on this, the whole pyramid building task is decomposed into several subtasks. The result of each subtask can be written to the same pyramid file simultaneously by incorporating MPI/IO. The algorithm can greatly improve the performance of pyramid building through parallel resampling and parallel I/O. Specially, with regard to the multi-band pyramid file stored in BIP format, a parallel I/O strategy using file view was proposed to improve the performance of parallel writing. Experimental results show that our algorithm has better acceleration effect compared to the sequential method, and there is a positive correlation between the acceleration effect and the image size. For large remote sensing images (in our case it is 46G), the performance of our parallel algorithm can be approximately 10 times faster than GDAL.

  • TANG Mengmeng, JI Genlin, ZHAO Bin
    Download PDF ( )   Knowledge map   Save

    Trajectory outlier detection is significantly important in the field of data mining for moving object. TRAOD (TRAjectory Outlier Dectection Algorithm), a classic algorithm for detecting trajectory outliers, focuses on a new two-level trajectory partitioning strategy to enhance the efficiency of algorithm. The main advantage of TRAOD algorithm is the ability to detect outlying sub-trajectories. However, it has a low efficiency on abnormality detection for massive trajectory data. In order to improve the efficiency for mining trajectory outliers from massive datasets, a parallel algorithm for detecting trajectory outliers based on MapReduce framework, which is called PTRAOD (Parallel algorithm for TRAjectory Outlier Detection), is presented. It redesigns the TRAOD algorithm based on the MapReduce framework, and encapsulates the steps of TRAOD into its Map and Reduce functions. PTRAOD algorithm takes full advantages of the features from Hadoop platform. It firstly distributes the trajectory data into distributed computing nodes. While distributing the data, it also takes the load-balance into consideration. And after all, each node runs the same algorithms to detect abnormal trajectories. Based on PTRAOD algorithm, a grid-based parallel algorithm for detecting trajectory outliers, called GPTRAOD (Gridbased Parallel algorithm for TRAjectory Outlier Detection), is then proposed. GPTRAOD algorithm makes use of the grid index to realize regional query and reduce unnecessary calculations. At first, GPTRAOD algorithm divides the map into a series of equal- sized grids, whose size is determined with respect to each specific data. Then, the grid index is established to implement the regional query. Finally, the algorithm finds out the abnormal trajectory segments and judges whether the trajectories that contains the abnormal trajectory segments are abnormal. In general, GPTRAOD algorithm takes advantages of the gird index to realize regional query on the basis of PTRAOD algorithm, which furthermore can search abnormal trajectory on the cloud computing platform. To assess the performances of the proposed algorithms, extensive experiments were conducted. The experimental results demonstrate that the proposed two parallel detection algorithms can both successfully achieve the trajectory outlier detection. The efficiency of PTRAOD algorithm is higher than TRAOD algorithm, while GPTRAOD algorithm has the higher scalability and better speedup ratio than PTRAOD algorithm. In addition, with the rapidly expanding of datasets, GPTRAOD algorithm shows obvious advantages and increasing potentials.

  • REN Yibin, CHEN Zhenjie, CHENG Liang, LI Manchun, PIAN Yuzhe
    Download PDF ( )   Knowledge map   Save

    With the development of high performance computing, parallel processing has been widely used in analyzing LiDAR point clouds. Aiming at the loading unbalancing problem that exists in current parallel algorithms for generating DEM from LiDAR point clouds, this research implements a parallel algorithm which uses dynamic load balancing strategy to generate DEM from massive LiDAR points. The parallel algorithm is based on the master- slave scheduling strategy. The master processor adaptively partitions LiDAR data and generates several strips afterwards. The data strip may be horizontal or vertical based on the characteristic of LiDAR data. The slave processors generate raster DEM from discrete LiDAR points using spatial interpolation. Furthermore, we propose a dynamic scheduling strategy based on the quantity of tasks. The quantity of each task is measured by the number of points in data strip. Firstly, all processors count the point number for all data strips and the master processor creates a task queue. The task queue is arranged according to the point number of those data strips in a descending order from the largest to the smallest. Secondly, the master processor communicates with the slave processors to distribute these tasks dynamically, thus to help the slave processors achieve the load balancing. In this way, all of the data strips are processed from the largest to the smallest based on the computational complexity. Finally, we test the proposed parallel algorithm in a cluster. The cluster is composed of 24 cores. The volume of the LiDAR point clouds for testing is 30 GB, which contains about 1.2 billion points. The resolution of the target DEM is 1 meter, and the biggest speedup ratio of the parallel algorithm is 15.16. At the same time, we compare the dynamic scheduling strategy proposed in this paper with the static scheduling strategy. The result shows that the dynamic scheduling strategy proposed in this research achieves a better load balancing among all processors. Therefore, we can come to a conclusion that the parallel algorithm proposed in this research can significantly improve the efficiency of generating DEM from massive LiDAR point clouds.

  • WEI Haitao, DU Yunyan, XU Kaihui, WU Di, YI Jiawei, MO Yang, LIU Zhang
    Download PDF ( )   Knowledge map   Save

    Parallel computing provides a promising solution to accelerate complicated spatial data processing, which is becoming increasingly computational intense. Partitioning large datasets into workload-balanced subgroups remains a challenge, particularly for unevenly distributed spatial data. In this study, a density-based data grouping algorithm was developed to tackle the partition problem for large line data. The algorithm includes three procedures: (1) extracting representative segment samples based on data density distribution; (2) generating a distance matrix between segment samples and the rest of the data by using three line distance measurements into calculations; (3) grouping line segments with data load balanced. Experiments show that the algorithm is able to partition large line data efficiently and evenly into equally sized sub-groups. The speed-up ratios of parallel interpolation save up to 65% of the execution time in comparison with consequential interpolation. A high efficiency of parallel computing was achieved when the datasets were divided into an optimal number of child data groups.

  • YOU Zhijie, XIE Chuanjie, MA Yihang, LONG Zhou
    Download PDF ( )   Knowledge map   Save

    The commonly used Plane Sweep algorithm in spatial relationship query is a serial algorithm. Some scholars had studied some parallel query algorithms that based on multi-core CPU. However, due to the limitations induced by the number of CPU's core and thread, when dealing with massive data query, these methods are incapable to meet the requirements for query efficiency. To solve this problem, this paper proposes a new parallel algorithm of spatial relationship query between polygon layers based on heterogeneous multi-core architecture. The algorithm used STR-tree index to filter the disjointed polygons first. After the filtration, we built a quadtree index to manage the line segments of the polygons, so that we could quickly get the line segment combination to prepare for computing the intersection situations. Then, the CPU+GPU architecture was adopted to parallel compute the line segments'intersection situation. In details, we firstly put each line segment combination into each thread of GPU to calculate the relevant intersection situation, and the intersection type was counted using CPU. Next, the topological relations between the polygon rings were judged according to the type of line segment intersection, thus the values of DE-9IM parameters between these polygons were calculated based on the topological relations, and accordingly, the spatial relationship between the polygons were determined. At last, the efficiency and accuracy of the algorithm was verified by an experiment. In the experiment, we gradually increased the polygon number of the source layer and the target layer. When both of the two layers had 50000 polygons, here took the Contains relation as an example, we found that the computation time of the parallel algorithm is 15.143s faster than ArcGIS, and the speedup ratio can reach up to 2. In general, the parallel algorithm has more obvious advantages in dealing with higher volumes of data.

  • WANG Chun, JIANG Ling, CHEN Taisheng, YANG Cancan
    Download PDF ( )   Knowledge map   Save

    The research approach based on sub-watershed partition, which is taken as an indispensable tool of spatial analysis in GIS applications, plays an important role in many research fields of watershed, such as landform, soil, hydrology and environment. Watershed codification usually is a key step in the research process via the above approach. Compared with some other watershed codification methods, Pfafstetter coding system is widely adopted due to its uniqueness of code, consideration of topological relationship and high efficiency. At present, with the development of spatial data acquisition technology, the quick acquisition of spatial data from large areas and with fine scales becomes a solid reality, which brings a great difficulty to GIS on how to process and analyze these massive datasets quickly and efficiently. Parallel computing brings an opportunity to face this challenge with the development of computer technology. In this paper, a parallel watershed codification algorithm was proposed to overcome the computation difficulties in processing the massive grid dataset. Firstly, the Pfafstetter coding rule was modified to compensate the disadvantages in the original algorithm including the incomplete coding and inconsistent code point. Secondly, data partition and parallel strategy were discussed based on the serial Pfafstetter coding algorithm and the requirements of data parallelism. At last, the parallel algorithm for watershed codification was realized and implemented. To evaluate the validity and the efficiency of the proposed parallel algorithm, experiments were designed on a cluster system with SRTM dataset covering the middle and upper watershed of Yangtze River. The experiment results showed that the parallel algorithm could generate correct results which were consistent with those in the real world; meanwhile, it possessed a significant improvement of computational efficiency. Besides the advantages in improving the computation ability and efficiency for the watershed codification algorithm, the parallel strategy in this paper could be further expanded as a reference to other researches on watershed analysis.

  • AI Beibei, QIN Chengzhi, ZHU Axing
    Download PDF ( )   Knowledge map   Save

    Parallel raster- based programming libraries have been proposed to make the details of parallel programming and the parallel hardware architecture to be transparent to users in some degrees. Thus these libraries can facilitate the development of parallel programs of raster-based geocomputation. Among the existing parallel programming libraries, parallel raster-based geocomputation operators (PaRGO), which is recently proposed by Qin et al, shows great advantages. This is not only because PaRGO encapsulates the general steps in parallel raster- based geocomputation, but also because PaRGO is compatible with multiple commonly used parallel computing platforms. Currently, PaRGO is designed for supporting local operation, focal operation and global operation directly. However, the availability of PaRGO for supporting regional operation in raster-based geocomputation has not been evaluated. In this paper, we evaluate PaRGO to testify its performance in this circumstance by using a multiple-flow-direction algorithm as a representation of the regional operation. Different versions of PaRGObased parallel programs for this algorithm are tested on a symmetrical multiprocessing (SMP) cluster and evaluated from two aspects: the performability and the parallel efficiency. The experimental results show that the current PaRGO cannot directly support the parallelization of regional operations. But it can be supportive when the regional operation is transformed into an iteration process of focal operation. On a SMP cluster, MPI-version parallel program performs better than MPI/OpenMP-version parallel program.

  • CHEN Cuiting, FANG Jinyun, QIU Qiang, YAO Xiao, LI Dongbin
    Download PDF ( )   Knowledge map   Save

    We study and propose the evaluation approach for parallel geo-computation algorithms from the following aspects: correctness evaluation, performance evaluation, evaluation routines and evaluation tools. This approach proposes the hypotheses for correctness evaluation which are viewed as the foundation of measuring the correctness of geo-computation algorithms. To measure the correctness, we compute the relative errors by comparing the results using a certain algorithm under the single-process with the corresponding results evaluated under the multi-process environment. In this paper, we present a method in which the weights of the evaluation cases are determined by the computation scale. We also discuss a method which computes the computation scale of evaluation cases. The method involves the data scale, data distribution coefficient and time consumption per unit computation. Meanwhile, the geo-computation algorithms are evaluated by cases with weights. Under some circumstances, we can obtain the various evaluation indicators of a certain algorithm, such as the execution time, the speedups, and the parallel efficiency. In addition, this paper designs an evaluation routine based on the correctness evaluation and performance evaluation. It obtains the correctness evaluation and performance indicators of our target algorithms and generates the final reports. After experiments, we may confirm that our techniques can meet the requirements for evaluating parallel geo-computation algorithms. It could provide an effective support to algorithm optimization.

  • HU Shujian, GUAN Qingfeng, GONG Junfang, LIU Yang, FAN Tianheng, YUN shuo
    Download PDF ( )   Knowledge map   Save

    Data I/O has become one of the main bottlenecks for parallel geospatial computing. In this study, we firstly explore the data structure of a widely used GIS raster data format-GeoTIFF, particularly focusing on its storage modes (strip storage and tile storage). The transfer functions which map the logical structure of data to the physical storage structure were constructed for both storage modes.This article also designs a framework for parallel I/O of raster data and implementsa parallel GeoTIFF I/O library (pGTIOL) using the file-view technique of MPI-IO. Experimental results showed that pGTIOL effectively enhances the I/O performance in comparison with the master-worker I/O mode which uses the Geospatial Data Abstraction Library (GDAL). pGTIOL encapsulates the underlying parallel I/O routines, and provides easy-to-use interfaces for the parallel reading and writing of GeoTIFF data. Compared with other parallel raster I/O software packages, pGTIOL supports a wide range of data types, both the strip and tile data storage modes, and various domain decomposition methods. Most importantly, pGTIOL supports asynchronous parallel I/O, which allows multiple processes to read and write sub-domains of data on demand.Hence,it could facilitate dynamic load-balancing in application.

  • LUO Laiping, ZHANG Jing, LI Yougang, HU Xinglin, MENG Tiantian
    Download PDF ( )   Knowledge map   Save

    To solve the problems about public transportation models in which the passenger behaviors and their interactions with public transportation are rarely concerned, a concept of virtual public transportation environment and the vector representation of its elements is proposed. Meanwhile, a transportation agent model and a passenger behavior agent model were built with the MAS method. Furthermore, an algorithm was proposed to simulate transportations, passengers, and the temporal and spatial variations in public transportation operation. Then, a prototype system of virtual public transport environment was implemented. In the end, a small-scale public transport environment, which was composed by7 roads, 8 bus routes, 31bus stops and 10 000 rides, was designed as the experiment environment. It produced 1428 bus runs and 30 436 passengers'swiping card data of getting on and off buses. The experimental data was analyzed while comparing with the average passenger waiting time under different departure intervals. The results show that the total travel time distribution is consistent with the input data, and the average waiting time is reduced if reducing the departure intervals of buses. It proves that the above models can effectively simulate public transportation environments. As a result, the traffic managers and researches could benefit from the prototype system and models, and it is helpful for them to make rational decisions.

  • WU Zhongjie, RUI Yikang, JIA Jian, NI Jianhua, WANG Jiechen
    Download PDF ( )   Knowledge map   Save

    With the development of service industry and promotion of culture industry, urban leisure and entertainment industry have gradually become an important symbol and driving force for urban economic and social development. KTV is a typical representative of the urban leisure and cultural entertainment services in China. Based on the geospatial entity data and business statistics data, this paper studies the market structure, spatial distribution and spatial expansion characteristics of KTV facilities in mainland China, using the spatial data visualization and the statistical analysis of GIS technology. Results show that KTV services have been rapidly developed and widely distributed across the whole country. The spatial distributions of KTV services were analyzed at national, provincial and city levels respectively, and they presented distinct characteristics including regional differentiation, urban hierarchy divergence, planar equalization, and central agglomeration. The relations between the spatial distribution and the influence factors, such as regional economy, population, and culture, were also investigated. All types of KTV facilities expand spatially from east to west and from the center to surrounding areas. In addition, among all types of KTV facilities, the KTV chains follow the geographical diffusion principles according to social economic phenomena research, which mainly include characteristics of hierarchy diffusion and contiguous diffusion.

  • ZHANG Rongqun, QIAO Yuexia, XUE Jiani
    Download PDF ( )   Knowledge map   Save

    Accurately get the spatial distribution of soil salinization and the spatial location characteristics of its relationship with land use intensity can explain the reason of soil salinization from a perspective of land use intensity, so as to provide a reference to local planning and management. In this paper, taking Yinchuan Plain as the research area, we primarily studied the method of getting the saline soil's spatial distribution based on remote sensing images. Combined with the land use remote sensing mapping and with the support of statistical methods based on semivariance function and grey correlation theory, the visual expression of spatial location distribution characteristics are developed for land use intensity change, soil salinization change, and the respond relationships between each kind of saline soil and land use intensity in Yinchuan plain. The main conclusions are presented as follows: first, the development of Yinchuan plain had an agglomeration effect. Land use intensity change was closely related to the urban system structure, the distribution of road and channels and soil salinity. Second, the soil salinization change of Yinchuan Plain revealed a spatial distribution of entire alleviation but local aggregation feature. The response relationship between saline soil and land use intensity change was spatial heterogeneity. Third, the correlation coefficient between the saline soil level change and land use intensity change was 0.7781. The correlation degree between land use and saline soil were found higher in water and cultivated land, which showed that the land use could influence soil salinization distribution characteristics. Therefore, among all the land use types, water and cultivated land were important factors of influence to soil salinization. Generally, strengthen the awareness of environmental protection and cultivation will help reduce soil secondary salinization. Further improve the water conservancy facilities can help reduce groundwater salinity. Moreover, we can protect cultivated land to promote the sustainable development of agriculture.

  • CHENG Xiaoli, HU Wenhai
    Download PDF ( )   Knowledge map   Save

    The existence of regional differences between tourism resources and tourism locations makes it necessary to analyze the spatial mismatch about regional tourism development and its causes, therefore to provide a scientific basis for promoting balanced development to regional tourism. With the assistance of gravity model and two-dimensional portfolio matrix,this article chooses tourism income, resource abundance and tourism location as the evaluation indices. Based on the research on 16 cities of Anhui province, we make a quantitative analysis of the spatial mismatch of tourism development and visualize the result using ArcGIS. The study shows that the spatial mismatch exists in tourism income, resource abundance and tourism location on different levels. The center of tourism income locates at 117.63°E and 31.18°N, the center of resource abundance locates at 117.51°E and 31.12°N, and the center of tourism location locates at 117.20°E and 32.00°N. In longitudinal direction, the largest spatial mismatch is 0.43°, and the minimum is 0.12°. In latitudinal direction, the largest spatial mismatch is 0.88°, and the minimum is 0.06°. Compared with the regional geometric center, the largest spatial mismatch in longitude and latitude direction appears in the center of tourism income and resource abundance, and both are relatively favoring southward. According to the combination matrix between tourism income and resource abundance, and that between tourism income and tourism location, 8 cities indicate mismatched development and the other 8 indicate synchronous development. Generally, tourism spatial mismatch in Anhui is mainly caused by the uneven allocation of tourism locations and tourism resources. To be specific, the main causes are: the resource distribution, that little of which distributed in the northern region, medium in the central region and lots in the southern region; and the traffic condition, that is mild in the northern region, heavy in the central region, and light in the southern region. According to the various characteristics of these cities, each city should make full use of regional advantages and exploit its own potentialities. The international tourism and cultural demonstration areas in the south of Anhui, in Wan-jiang urban belt, in Hefei economic circle, and in the tourism region of north Anhui should take different spatial correction strategies to promote the development of regional tourism collaboratively.

  • NING Wenyan, LU Liang, REN Hongyan, LIU Qiyong
    Download PDF ( )   Knowledge map   Save

    Dengue fever is an acute insect-borne disease transmitted by the Aedes mosquito, which is a class B infectious disease in China. Understanding the variations occurred in the spatial and temporal distribution of dengue fever epidemics will bring improvements to dengue fever prevention and control. In this study, monthly incidence data for dengue fever at municipality level across China were analyzed for the period from 2004 to 2013. The relationships between the incidence rates of dengue fever, the involved municipalities, and the imported cases were determined. The geographic pattern of dengue fever incidence rates was examined by GIS, spatial autocorrelation analysis and from the tracks of the centre of mass. Results showed that: (i) annually, the incidence rates for indigenous dengue fever cases exhibited the highest values between August and October, while the imported cases peaked between July and October. (ii) The logarithmic values of indigenous dengue fever cases was significantly correlated with the numbers of imported cases (r=0.669, p<0.05), while the number of municipalities with imported cases was linearly correlated to the number of all municipalities that have dengue fever cases (r=0.939, p<0.05). (iii) In addition to the increasing incidence rate, the dengue fever epidemic was affecting an increasing number of municipalities. The range of the epidemic was steadily increasing and gradually spreading toward inland area from the southeastern coast. (iv) Dengue fever cases did not distributed randomly with respect to time and geographical space. The highest density occurred in areas of Pearl River Delta, Hanjiang River Delta, Dehong prefecture, and Xishuangbanba prefecture. The centre of mass of dengue fever incidence rates was not stable and moved from the southeast coast (Fujian and Guangdong provinces) to the southwest (border of Yunnan province), which revealed the changes of the dengue fever distribution pattern. Our results indicate that the dengue fever epidemic in China is driven by imported cases from other countries. According to the temporal and spatial characteristics of the increasing incidence rates at municipality level and the expanding range of dengue fever in China, a stronger border inspection for people entering from abroad, especially from Southeast Asia and during the peak epidemic months between July and October, may be effective in preventing the spread of this rising epidemic.

  • XU Yunhe, FANG Bin
    Download PDF ( )   Knowledge map   Save

    The distribution of organic matters in tea garden soil shows an obvious spatial pattern. Methods to predict the distribution of organic matters in the study region using data from a limited series of sampling points is very important in studying the soil status of tea gardens, providing guidance to manage tea gardens, and improving tea quality and products. In this paper, we made a research on 4 famous tea planting areas in Jiangsu Province and Zhejiang Province, and we conducted a comparative analysis on the spatial heterogeneity of the organic matters in tea garden soil using descriptive statistics and geostatistics, which included the semi-variogram model and the spatial interpolation diagram analysis. Furthermore, we explored the spatial distribution characteristics of the organic matters in tea garden soil and its influencing factors. The results showed that: (1) the average level of the soil organic matters in all of the four study areas was favorable for tea growth. In addition, the average level of soil organic matters in Zhejiang Province was higher than that in Jiangsu Province. (2) The semi-variance function models proposed that a medium spatial correlation existed in the organic content of Xilong growing area, while a strong spatial correlation was discovered in the other three areas. The interpolation map showed that regions with high organic content in the two study areas of Zhejiang was had broader ranges than the other two study areas in Jiangsu. (3) We also conducted a qualitative analysis on factors influencing the spatial distribution of organic matters, based on relevant literatures, investigations and data. As a result, we found that the spatial distribution of organic matters in each area was determined by the structural factors, such as the soil physicochemical properties and the characteristics of landforms. Moreover, the random factors, such as human activities, business operation modes, tea garden management, and proper protection strategies, also had local impacts on the distribution of organic matters.