Parallel creation of vario-scale data structures for large datasets

Abstract

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.