Abstract: To improve the retrieval speed of the map in an embedded navigation system, an algorithm of dynamic partition is introduced in this paper. According to the number of map features, the algorithm divided the map into several grids. Through increasing the store space cost to reduce the retrieval time, the real time performance of the algorithm was improved. After map partition, the fusing map matching algorithm was realized, which amalgamated road topological relation and D-S evidence reasoning. The simulation result shows that the proposed algorithm has better matching accuracy and it could improve the real time capability and adaptability of the navigation system.