Design & Optimization Of Embedded GIS Based On Nand Flash

With development of Embedded computing, NAND is pervasive in this environment as an efficient storage device. Benefiting from the enhancement of hardware & software performance, GIS is popular in the Embedded platform. In GIS, the performance is mostly determined by the index structure of space data, and now the general index structure is variants of R-Tree based on hard disk. This paper introduces a more efficient variants of R-Tree, and do some optimization works directed towards unique Read & Write feature of NAND Flash.This paper includes two major parts:(1) Introduces a new index structure R~d-Tree derived from R~o-Tree. R~o-Tree introduces the conception of outlier object which is far away from any other objects in the node. By moving the outlier objects from a node to its parent node, it can decrease the overlapping area between children nodes. R~d-Tree is an index structure based on node density which is an important index to measure the node quality. The main idea of R~d-Tree is organizing the nodes with similar features together. In reality, the nodes with similar features are often adjacent with each other. R~d-Tree improves R~o-Tree through such aspects: First improving the outlier object differentiation algorithm in inserting process, in R~d-Tree we do not treat a node as an outlier if after its insertion the node density of parent node is not decreased. This algorithm improves the node quality and decreases the number of outlier objects. Second optimizing the deleting process, when a node underflows in the deleting process, R~d-Tree borrows a outlier object from parent node to prevent meaningless reinserting operation. Third improving the searching efficiency, as R~d-Tree decreasing the number of outlier objects, the comparing times in the searching process will be less. For example, for the classical range query, R~d-Tree is with 20 percent gain to R~o-Tree.(2) Imports the journal mechanism according to physical features of NAND Flash. NAND is a kind of write-once device, updating the source data will produce large sum of garbage pages, in turn, decrease the available space and cause frequent garbage collection operation which will erase the NAND. So in this paper, we divide the map into index data file and update data file, and the update is appended to the update data file as journal. Each time we open the map, the update will be committed to the index and then generate a new index in memory. With consideration of efficiency, we study the compaction of map, when the update data is too large the rebuilding process will be long, in such situation we write the new index tree to the NAND and delete the original index data and update data.