Research And Implementation Of Distributed Parallel Map Matching System

This dissertation designed and realized a distributed parallel map matching system for the purpose of processing map matching quickly in mass float car data condition; we mainly discussed the following three issues:Firstly, this paper depicted the design of distributed parallel map matching system under multi-core cluster structure. We selected the Windows HPC Server2008R2as the cluster environment and constructed the cluster according to the network topology. To address the issue of inability to utilize the resources of multi-core processor sufficiently under the Message Passing Interface (MPI) model, we combined the MPI with shared memory programming model to form a hybrid parallel programming model and exploited the multi-core cluster computing resources efficiently through the two-stage parallelism. After analyzing the features of the map matching data streams, we considered that the data parallelization is the most suitable task parallelization policy to the cluster.Secondly, our research proposed an innovative algorithm to address the issue of primary filtering of pre-matching road. Current methods for primary filtering of pre-matching road used the redundant grid policy to ensure the confidence level of grid. To eliminate this deficiency, this paper designed a quantification computing method for the grid confidence level and devised a new algorithm of primary filtering of pre-matching road according to the theoretical foundations that the smaller distance between the pre-localization point and the grid center, the higher level of the grid confidence. This paper discussed the new grid partition rule and the new grid indexing computing into details and evaluated on the algorithm complexity and the ability of optimization.Thirdly, we explored the usage of main memory database (MMDB). In this paper, we proposed the idea of using MMDB to avoid the disk database I/O cost during the high frequency searching and employed the SQLite MMDB as the experimental instance to trace the optimization outcome after applying the MMDB to matching system. We performed a prototype of the distributed parallel map matching system based on above work and conducted three experiments to validate our proposed methodologies from the aspects of the primary filtering algorithm for pre-matching road, the different data store method and the parallel programming model. Experiments demonstrated the following conclusive results:a) the proposed primary filtering algorithm could promote the efficiency of processing with a gain of1～3; b) the SQLite MMDB could speed up the matching process by160%; c) the hybrid programming model could obtain a speedup at1.7～2.0for the efficiency of system processing. Our research fruits provided a practical promising solution to tackle the problem of the large-scale floating car data processing.