Journal of Korea Spatial Information System Society (한국공간정보시스템학회 논문지)

Korea Spatial Information System Society (대한공간정보학회)
권호 표지

An Efficient Spatial Index Technique based on Flash-Memory

플래시 메모리 기반의 효율적인 공간 인덱스 기법

  • Published : 2009.06.30
Download PDF
⟨ Previous Next ⟩

Abstract

Recently, with the advance of wireless internet and the frequent use of mobile devices, demand for LBS(Location Based Service) is increasing, and research is required on spatial indexes for the storage and maintenance of spatial data to provide efficient LBS in mobile device environments. In addition, the use of flash memory as an auxiliary storage device is increasing in order to store large spatial data in a mobile terminal with small storage space. However, the application of existing spatial indexes to flash-memory lowers index performance due to the frequent updates of nodes. To solve this problem, research is being conducted on flash-memory based spatial indexes, but the efficiency of such spatial indexes is lowered by low utilization of buffer and flash-memory space. Accordingly, in order to solve problems in existing flash-memory based spatial indexes, this paper proposed FR-Tree (Flash-Memory based R-Tree) that uses the node compression technique and the delayed write operation technique. The node compression technique of FR-Tree increased the utilization of flash-memory space by compressing MBR(Minimum Bounding Rectangle) of spatial data using relative coordinates and MBR size. And, the delayed write operation technique reduced the number of write operations in flash memory by storing spatial data in the buffer temporarily and 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. Finally, we perform ed various performance evaluations and proved the superiority of FR-Tree to the existing spatial indexes.

최근 무선 인터넷이 발전하고 모바일 단말기 사용이 증가함에 따라 위치 기반 서비스(LBS: Location Based Service)에 대한 요구가 증가되고 있으며, 모바일 단말기 환경에서 효율적인 위치 기반 서비스를 제공하기 위해 공간 데이타를 저장 및 관리하는 공간 인덱스의 연구가 필수적으로 요구되고 있다. 플래시 메모리는 모바일 단말기에서 대용량의 공간 데이타를 효율적으로 저장하기 위한 보조 저장 장치로 많이 사용된다. 그러나 플래시 메모리에 기존 공간 인덱스를 그대로 적용할 경우 빈번한 노드 갱신에 의한 쓰기 연산 증가로 인덱스 성능이 저하된다. 이러한 문제점을 해결하고자 최근 플래시 메모리 기반 공간 인덱스가 연구되고 있지만 버퍼와 플래시 메모리의 공간 활용도가 낮아 효율성이 떨어지는 문제점이 있다. 따라서, 본 논문에서는 기존의 플래시 메모리 기반 공간 인덱스들의 문제점을 해결하기 위해 노드 압축 기법과 쓰기 연산 지연 기법을 적용한 FR-Tree(Flash-Memory based R-Tree)를 제안하였다. FR-Tree의 노드 압축 기법은 공간 데이타의 MBR(Minimum Bounding Rectangle)을 상대 좌표값과 MBR 크기 값을 이용해 압축함으로써 플래시 메모리의 공간 활용도를 높였다. 그리고 쓰기 연산 지연 기법은 공간 데이타의 삽입, 갱신, 삭제시 플래시 메모리에 저장된 공간 인덱스에 바로 반영하지 않고 버퍼에 임시적으로 저장한 후 일괄적으로 플래시 메모리에 반영하여 플래시 메모리의 쓰기 연산 횟수를 줄였다. 특히, 버퍼내 동일한 공간 데이타들의 중복 저장을 방지하여 버퍼의 공간 활용도를 높였다. 마지막으로, 본 논문에서는 다양한 성능 평가를 통해 FR-Tree가 플래시 메모리에서 기존 공간 인덱스들에 비해 성능이 우수함을 입증하였다.

Keywords

References

  1. Forlizzi, L., Gueting, R.H., Nardelli, E., and Schneider, M., “A Data Model and Data Structures for Moving Objects Databases,” Proc. of the ACM SIGMOD Conference, 2000, pp. 319-330.
  2. Niedzwiadek, H., “OpenLS-1 Interoperability Project: An Overview,” LBS Forum Foundation Meeting and Celebration Seminar, 2002, pp. 30-51.
  3. 이기영, 윤재관, 한기준, “HBR-Tree를 이용한 실시간 모바일 GIS의 개발,” 개방형지리정보시스템학회논문지, 제6권 제1호, 2004, pp. 75-85.
  4. Byun, S.W., “An Index Rewriting Scheme Using Compression for Flash Memory Database Systems,” Journal of the Information Science, Vol.33 No.4, 2007, pp. 398-415. https://doi.org/10.1177/0165551506076331
  5. Wu, C.H., Chang, L.P., and Ku, T.W., “An Efficient R-Tree Implementation over Flash-Memory Storage Systems,” Proc. of the ACM International Symposium on Advances in Geographic Information Systems, 2003, pp. 17-24.
  6. Wu, C.H., Chang, L.P., and Kuo, T.W., “An Efficient B-Tree Layer for Flash-Memory Storage Systems,” Proc. of the International Conference on Real-Time and Embedded Computing Systems and Applications, 2003, pp. 409-430.
  7. 김정준, 강홍구, 김동오, 한기준, “메인 메모리 다차원 인덱스를 위한 효율적인 MBR 압축 기법,” 한국공간정보시스템학회 논문지, 제9권 제2호, 2007, pp. 13-23.
  8. SAMSUNG Electronics, 512M ${\times}$ 8 Bit / 1G ${\times}$ 8 Bit NAND Flash Memory, 2005.
  9. 이수관, 민상렬, 조유근, “플래시 메모리 관련 최근 기술 동향,” 정보과학회지, 제24권 제12호, 2006, pp.99-106.
  10. Guttman, A., “R-Trees: a Dynamic Index Structure for Spatial Searching,” Proc. of the ACM SIGMOD Conference, 1984, pp. 47-54.
  11. Lee, T.W., Moon, B.K., and Lee, S.H., “Bulk Insertion for R-trees by Seeded Clustering,” Proc. of the Data and Knowledge Engineering, Vol.59 No.1, 2006, pp. 86-106.