메인 메모리 다차원 인덱스를 위한 효율적인 MBR 압축 기법 = An Efficient MBR Compression Technique for Main Memory Multi-dimensional Indexes

국문 초록 (Abstract)

최근 실시간 서비스의 요구 사항을 갖는 위치 기반 서비스와 텔레매틱스 서비스를 효율적으로 제공하기 위해서 공간 메인 메모리 DBMS에 대한 관심이 급증하고 있다. 이러한 공간 메인 메모리 DBMS에서 기존의 디스크 기반 다차원 인덱스들을 메인 메모리에 최적화하기 위해 엔트리 크기를 줄여 캐시 접근 실패를 최소화한 다차원 인덱스 구조들이 제안되고 있다. 그러나 엔트리 크기를 줄이기 위하여 부모 노드의 MBR을 기준으로 압축하거나 중복된 MBR을 제거하기 때문에 인덱스 갱신 시 MBR 재구성 비용이 증가하고 인덱스 검색 시 효율이 떨어지는 문제점이 있다. 본 논문에서는 MBR 재구성 비용을 줄이기 위하여 넓은 분포의 경우와 좁은 분포의 경우로 나누어 압축 기준점을 다르게 적용하는 RSMBR(Relative-Sized MBR) 압축 기법을 제시하였다. RSMBR 압축 기법은 넓은 분포일 경우 부모 노드 확장 MBR의 좌하점을 기준으로 압축하고, 좁은 분포일 경우 전체 MBR을 일정 크기의 셀로 나누고 각 셀의 좌하점을 기준으로 압축한다. 또한 인덱스 검색 시 검색 비용을 줄이기 위하여 상대 좌표와 크기를 이용하여 MBR을 압축한다. 마지막으로, 본 논문에서는 실제 데이타를 통한 성능 평가를 수행하여 RSMBR 압축 기법의 우수성도 입증하였다.

다국어 초록 (Multilingual Abstract)

Recently there is growing Interest in LBS(Location Based Service) requiring real-time services and the spatial main memory DBMS for efficient Telematics services. In order to optimize existing disk-based multi-dimensional Indexes of the spatial main memory DBMS in the main memory, multi-dimensional index structures have been proposed, which minimize failures in cache access by reducing the entry size. However, because the reduction of entry size requires compression based on the MBR of the parent node or the removal of redundant MBR, the cost of MBR reconstruction increases in index update and the efficiency of search is lowered in index search. Thus, to reduce the cost of MBR reconstruction, this paper proposed the RSMBR(Relative-Sized MBR) compression technique, which applies the base point of compression differently in case of broad distribution and narrow distribution. In case of broad distribution, compression is made based on the left-bottom point of the extended MBR of the parent node, and in case of narrow distribution, the whole MBR is divided into cells of the same size and compression is made based on the left-bottom point of each cell. In addition, MBR was compressed using a relative coordinate and size to reduce the cost of search in index search. Lastly, we evaluated the performance of the proposed RSMBR compression technique using real data, and proved its superiority.

참고문헌 (Reference)

1 Kim, J. J, "TMOM: A Moving Object Main Memory-Based DBMS for Telematics Services" 259-268, 2006

2 Guttman, A, "R-Trees: a Dynamic Index Structure for Spatial Searching" 47-54, 1984

3 Kim, K, H, "Optimizing Multidimensional Index Tree for Main Memory Access" 139-150, 2001

4 Rao, J, "Making B+-Trees Cache Conscious in Main Memory" 475-486, 2000

5 Bohannon, P, "Main-Memory Index Structures with Fixed-Size Partial Keys" 163-174, 2001

6 Mindaugas, P, "Indexing the Past, Present, and Anticipated Future Positions of Moving Objects" 255-298, 2006

7 Chen, S, "Improving Index Performance through Prefetching" 235-246, 2001

8 Chen, S, "Fractal Prefetching B+-Trees : Optimizing Both Cache and Disk Performances" 157-168, 2002

9 Yun, J. K, "Development of an Embedded Spatial MMDBMS for Spatial Mobile Devices" 1-10, 2005

10 Boncz, P, "Database Architecture Optimized for the New Bottleneck : Memory Access" 54-65, 1999

11 Sitzmann, I, "Compacting Discriminator Information for Spatial Trees" 167-176, 2002

12 Zhou,J, "Buffering Accesses of Memory-Resident Index Structures" 405-416, 2003

13 Shim, J, M, "An Efficient Cache Conscious Multi-dimensional Index Structure" 869-876, 2004