A spatially adaptive decomposition approach for parallel vector data visualization of polylines and polygons

Abstract

With the wide adoption of big spatial data and the emergence of CyberGIS, the nontrivial computational intensity introduced by massive amount of data poses great challenges to the performance of vector map visualization. The parallel computing technologies provide promising solutions to such problems. Evenly decomposing the visualization task into multiple subtasks is one of the key issues in parallel visualization of vector data. This study focuses on the decomposition of polyline and polygon data for parallel visualization. Two key factors impacting the computational intensity were identified: the number of features and the number of vertices of each feature. The computational intensity transform functions (CITFs) were constructed based on the linear relationships between the factors and the computing time. The computational intensity grid (CIG) can then be constructed using the CITFs to represent the spatial distribution of computational intensity. A noninterlaced continuous space-filling curve is used to group the lattices of CIG into multiple sub-domains such that each sub-domain entails the same amount of computational intensity as others. The experiments demonstrated that the approach proposed in this paper was able to effectively estimate and spatially represent the computational intensity of visualizing polylines and polygons. Compared with the regular domain decomposition methods, the new approach generated much more balanced decomposition of computational intensity for parallel visualization and achieved near-linear speedups, especially when the data is greatly heterogeneously distributed in space.

Keywords:

• vector map
• visualization
• load-balance
• decomposition
• computational intensity

Notes

1. In this study, we used the Microsoft Graphics Device Interface (GDI) for map rendering.

2. This is often the case in many parallel computing systems. More research will be conducted on heterogeneous parallel systems whose computing units have differentiated computing capacities, to investigate the optimal load-balancing approaches for parallel map visualization.

3. The choice of data layers can be scale-dependent, meaning the layers with appropriate details for the desired map scale are chosen.

4. The decompositions of the polyline datasets are similar to those of the polygon datasets.

Additional information

Funding

This study was funded by the Specialized Research Fund for the Doctoral Program of Higher Education, Ministry of Education of China [20130145120013]; China Postdoctoral Science Foundation [2014M552115]; and was supported by the Fundamental Research Funds for the Central Universities, China University of Geosciences (Wuhan) [CUGL140833].