Parallel creation of vario-scale data structures for large datasets

Parallel creation of vario-scale data structures for large datasets

Meijers, B.M.
Suba, R.
van Oosterom, P.J.M.

Architecture and The Built Environment

OTB

2015-12-31

Processing massive datasets which are not fitting in the main memory of computer is challenging. This is especially true in the case of map generalization, where the relationships between (nearby) features in the map must be considered. In our case, an automated map generalization process runs offline to produce a dataset suitable for visualizing at arbitrary map scale (vario-scale) and efficiently enabling smooth zoom user interactions over the web. Our solution to be able to generalize such large vector datasets is based on the idea of subdividing the workload according to the Fieldtree organization: a multi-level structure of space. It subdivides space regularly into fields (grid cells), at every level with shifted origin. Only features completely fitting within a field are processed. Due to the Fieldtree organization, features on the boundary at a given level will be contained completely in one of the fields of the higher levels. Every field that resides at the same level in the Fieldtree can be processed in parallel, which is advantageous for processing on multicore computer systems. We have tested our method with datasets with upto 880 thousand objects on a machine with 16 cores, resulting in a decrease of runtime with a factor 27 compared to a single sequential process run. This more than linear speed-up indicates also an interesting algorithmic side-effect of our approach.

Large datasets
parallel processing
generalization
vario-scale data structures

http://resolver.tudelft.nl/uuid:d86b7aa3-5192-4ead-96bc-0901cad90208

ISPRS

2194-9050

The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XL-4/W7, 2015, 4th ISPRS International Workshop on Web Mapping and Geoprocessing Services, 01 – 03 July 2015, Sardinia, Italy

Institutional Repository

conference paper

(c) 2015 Meijers, B.M.
Suba, R.
van Oosterom, P.J.M.