Research And Implementation On Parallel Bulk-loading Algorithm For Spatial Index

In the GIS field, with the development of database technology, spatial database technology is experiencing flourish. At the same time as the increase in massive spatial data, spatial index is important to spatial data retrieval. In recent years, computer processor is transforming from high-frequency single-core processors to on-chip multi-core processors (CMP, Chip Multi-Processor), and from thread-level parallelism to instruction-level parallelism. Parallel computing model is receiving more and more attention, which is also applied by the many practical applications. Although the problem of index bulk-loading has been studied by many researchers, the parallel version of the problem did not receive the required attention. Based on comprehensive study of spatial index and parallel computing, this paper mainly focuses on the following aspects:1) Cost model based parallel bulk-loading algorithms for spatial indexIntegrated with R-tree based data access methods, the paper first describes processing steps and algorithms of dynamic R-tree like indices. Besides, shortages of dynamic algorithms in managing massive spatial is discovered and presented. Then, the paper illustrates the advantages of static counterparts compared with dynamic algorithms, which are suitable for spatial queries in spatial database. At last, the cost model of parallel bulk-loading of spatial data is presented.2) Parallel bulk-loading algorithms of spatial dataBased on the analysis of traditional Hilbert R-tree index building algorithms, its parallel potential is explored. For CMP (chip multi-processor), traditional bulk-loading algorithms need to be improved urgently. The paper design and implement parallel bulk-loading algorithms of R-tree like index. Experiments validate its efficiency and correctness on total running time, parallel efficiency and the speedup.3) Memory management for the parallel bulk-loading algorithmThe potential memory management problems of forenamed algorithms are addressed. A more efficient memory strategy is proposed to accommodate the parallel requirements. Then, to avoid memory leak, a memory garbage recycling algorithm is studied. Finally, the paper compares the performance of parallel bulk-loading algorithm with the former one.4) Experimental system of parallel bulk-loading based on the QGISOn current mainstream open-source GIS software, the paper analyses their development platform and programming language, and focuses on development of open source software as well as performance characteristics. The paper explores a spatial index bulk-loading experiments prototype with external plug-in in parallel systems.In conclusion, based on CMP, the paper designs and implements parallel bulk-loading algorithms of spatial R-tree like indices, proposes an efficient memory management strategy working with the algorithms, and validates all the research results.