Spatial Access Method for Flash Memory Embedded Systems

Abstract:

This paper proposed an efficient spatial Access method, called MDR-Tree (Mbr compression and Delayed write operation based R-Tree), that uses the node compression technique and the delayed write operation technique for flash memory embedded systems. The node compression technique of MDR-Tree increased the utilization of flash memory space by compressing the MBR of spatial data using relative coordinates and MBR size. Moreover, the delayed write operation technique reduced the number of write operations in flash memory by temporarily storing spatial data in the buffer and by reflecting them in flash memory at once instead of reflecting the insert, update and delete of spatial data in flash memory for each operation. Especially, the utilization of buffer space was enhanced by preventing the redundant storage of the same spatial data in the buffer.

• Periodical: Advanced Materials Research (Volumes 403-408)
• Pages: 4311-4317
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.403-408.4311
• Online since: November 2011
• Authors: Ki Young Lee, Joung Joon Kim, Myung Jae Lim, Kyu Ho Kim, Jeong Lae Kim
• Keywords: Embedded System, Flash Memory, R-Tree, Spatial Access Method

References

[1] C. H. Wu, L. P. Chang, and T. W. Kuo, An efficient r-tree implementation over flash-memory storage systems, Proc. of the ACM International Symposium on Advances in Geographic Information Systems, (2003), p.17–24.

DOI: 10.1145/956676.956679

[2] C. I. Park, J. Y. Seo, D. Y. Seo, S. H. Kim, and B. S. Kim, Cost-efficient memory architecture design of NAND flash memory embedded systems, Proc. of the International Conference on Computer Design, (2003), pp.474-479.

DOI: 10.1109/iccd.2003.1240943

[3] Guttman, R-Trees: a dynamic index structure for spatial searching, Proc. of the ACM SIGMOD Conference, (1984), pp.47-54.

DOI: 10.1145/971697.602266

[4] J. J. Kim, H. K. Kang, D. S. Hong, and K. J. Han, An efficient compression technique for a multi-dimensional index in main memory, Proc. of the International Conference on Visual Information Systems, (2007), pp.336-346.

[5] SAMSUNG Electronics, 512M × 8 Bit / 1G × 8 Bit NAND Flash Memory, (2005).

[6] S. W. Byun, An index rewriting scheme using compression for flash memory database systems, Journal of the Information Science, vol. 33, no. 4, (2007), pp.398-415.

DOI: 10.1177/0165551506076331