실시간 모바일 GIS 응용 구축을 위한 주기억장치 데이터베이스 시스템 설계 및 구현
Design and Implementation of a Main-Memory Database System of Real-time Mobile GIS Application
1
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
최근 들어 계속되는 램 가격 하락으로 인해 대용량의 램을 사용하는 주기억장치 데이터베이스 시스템의 구축이 실현 가능하게 되었다. 주기억장치 데이터베이스는 여러 다양한 실시간 응용 분야를 위해 사용되며, 매년 CPU 속도가 60% 정도 증가되고, 메모리 속도가 10% 증가되는 현실에서, 케쉬 미스(Cache miss)를 얼마나 줄이느냐 하는 문제가 주기억장치 데이터베이스의 검색 성능 측면에서 가장 중요한 문제로 대두되고 있다. 본 논문에서는 이러한 환경을 고려한 실시간 모바일 GIS응용을 위한 주기억장치 데이터베이스 시스템을 설계 및 구현한다. 본 시스템은 크게 PDA를 사용하는 모바일 사용자를 위한 인터페이스 관리기와 가상 메모리 기법을 사용해 전체 데이터를 주기억 장치에 상주시키며 관리하는 주기억 데이터 관리기, 공간 및 비공간 질의를 처리하는 질의처리기, 새롭게 제시하는 공간 데이터를 위한 MR-트리 인덱스와 비공간 데이터를 위한 T-트리 인덱스 구조를 관리하는 인덱스 관리기, 데이터를 디스크에 저장하기 위한 GIS 서버 인터페이스로 구성된다. 새롭게 제시하는 공간 인덱싱을 위한 MR-트리는 노드 분할이 발생될 경우, 입력 경로 상에 하나 이상의 빈 엔트리를 지니는 노드가 존재할 경우에만, 노드 분할을 상위로 전송한다. 그러므로 중간 노드들은 항상 100%에 가깝게 채워져 있게 된다. 본 논문의 실험 결과, 2차원의 MR-트리는 기존의 R-트리에 비해 2.4배 이상의 빠른 검색 속도를 나타냈다. 한편, 주기억 데이터 관리기는 가상 메모리 제공을 위해 전체 벡터 데이터 및 MR-트리, T-트리, 데이터 객체 텍스트 정보를 페이지 단위로 분할하여 관리하고, 간접 주소 기법을 사용하여 디스크로부터의 재로딩시 발생할 수 있는 문제점을 제거하였다.
Abstract
As random access memory chip gets cheaper, it becomes affordable to realize main memory-based database systems. Consequently, reducing cache misses emerges as the most important issue in current main memory databases, in which CPU speeds have been increasing at 60% per year, compared to the memory speeds at 10% per year. In this paper, we design and implement a main-memory database system for real-time mobile GIS. Our system is composed of 5 modules：the interface manager provides the interface for PDA users；the memory data manager controls spatial and non-spatial data in main-memory using virtual memory techniques；the query manager processes spatial and non-spatial query；the index manager manages the MR-tree index for spatial data and the T-tree index for non-spatial index；the GIS server interface provides the interface with disk-based GIS. The MR-tree proposed propagates node splits upward only if one of the internal nodes on the insertion path has empty space. Thus, the internal nodes of the MR-tree are almost 100% full. Our experimental study shows that the two-dimensional MR-tree performs search up to 2.4 times faster than the ordinary R-tree. To use virtual memory techniques, the memory data manager uses page tables for spatial data, non-spatial data, T-tree and MR-tree. And, it uses indirect addressing techniques for fast reloading from disk.
참고문헌 (14)
- K. Kim, "Optimizing Multidimensional Index Trees for Main Memory Access", pp.139~150 (2001)
- Trishul M. Chilimbi, "Making Pointer-Based Data Structures Cache Conscious", pp.67~74 (2000)
- P. Bones,S. Manegold, "Database Architecture Opimized for the New Bottleneck：Memory Access", pp.54~65 (1999)
- A. Ailamaki, "DBM Ss on a Modern Processor：Where Does Time Go", pp.267~277 (1999)
- J. Rao,K. A. Ross, "Cache Conscious Indexing for Decision-support in Main Memory", pp.78~89 (1999)
- J. Rao,K, "Making B+-trees Cache Conscious in Main Memory", pp.475~486 (2000)
- A. Guttman, "R-tree：A Dynamic Index Structure for Spatial Searching", pp.47~57 (1984)
- Phi Bernstein, "The Asilomar report on database research", 27((4)) (1998)
- Bohannon, "The Architecture of the Dali Main Memory Storage Manager" (1997)
- H. V. Jagadish, "DaliA High Performance Main Memory Storage Manager^Santiago" (1994)
- L. Felician, "A nearly optimal Huffman technique in the microcomputer environment Inf. Sys. 12, 4", pp.12~ (1987)
- R. G. Gallager, "Variations on a Theme by Huffman IEEE Trans. on Inf. Theory IT-24" (1978)
- Tobin J. Lehman, "An Evaluation of Starburst’s Memory Resident Storage Componet", 4 (1992)
- Tobin J. Lehman, "A Study of Index Structures for Main Memory Database Management Systems Procedings 12th Int’l. conf. on Very Large Databases", pp.294~303 (1986)