An efficient R-tree implementation over flash-memory storage systems

ABSTRACT

For many applications with spatial data management such as Geographic Information Systems (GIS), block-oriented access over flash memory could introduce a significant number of node updates. Such node updates could result in a large number of out-place updates and garbage collection over flash memory and damage its reliability. In this paper, we propose a very different approach which could efficiently handle fine-grained updates due to R-tree index access of spatial data over flash memory. The implementation is done directly over the flash translation layer (FTL) without any modifications to existing application systems. The feasibility of the proposed methodology is demonstrated with significant improvement on system performance, overheads on flash-memory management, and energy dissipation.

REFERENCES

• 1: Esri shape file technical description. Technical report, ESRI.
• 2: Ftl logger exchanging data with ftl systems. Technical report,Intel Corporation.
• 3: Understanding the flash translation layer(ftl) specification. Technical report, Intel Corporation.
• 4: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 5: M. R. Garey and D. S. Johnson. Computers and intractability 1979.
• 6: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 7: Han-joon Kim , Sang-goo Lee, A New Flash Memory Management for Flash Storage System, 23rd International Computer Software and Applications Conference, p.284, October 19-26, 1999
• 8: A. Kawaguchi, S. Nishioka, and H. Motoda. A flash-memory based file system. USENIX Technical Conference on Unix and Advanced Computing Systems, 1995.
• 9: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 10: C. H. Wu, L. P. Chang, and T. W. Kuo. An efficient b-tree layer for flash-memory storage systems. The 9th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA 2003), 2003.
• 11: Michael Wu , Willy Zwaenepoel, eNVy: a non-volatile, main memory storage system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.86-97, October 05-07, 1994, San Jose, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Design, Performance

Keywords:
GIS, R-tree, embedded systems, flash memory, spatial index structures, storage systems