공간데이타베이스를 위한 효율적인 병렬형 공간색인구조 = Efficient Parallel Spatial Index Structure for Spatial Databases

국문 초록 (Abstract)

공간 index structure는 공간 data를 효율적으로 관리하기 위한 도구로써, 공간 database의 performance를 결정하는 중요한 요소라 하겠다. 대부분의 application에서 방대한 양의 공간 data가 보조기억장치(예 : disk)에 저장이 되어 사용이 된다. 공간 index structure의 operation은 I/O에 대한 의존도가 크므로, I/O operation의 병렬처리는 공간 index structure의 query반응시간을 현저하게 줄일 수 있다. 또한 여러 개의 disk를 사용하는 병렬처리는 방대한 양의 공간 data를 저장하는데 적당하다. 본 논문에서는 PML-tree라는 공간 index structure를 제안한다.
PML-tree는 object distribution heuristics를 사용하여 data object를 여러 개의 data space에 균일하게 배치함으로써 query processing의 속도를 향상시킨다. 두 가지의 object distribution heuristics(absolute crowd index와 relative crowd index)가 제안이 된다. PML-tree는 R-tree계열의 구조로써 기존의 R-tree계열의 구조들과 유사한 node의 형태를 가지고 있으나, data object를 분배함으로써 R?-tree의 leaf node내에 존재하는 redundancy를 제거하면서, R-tree의 단점인 index rectangle들 사이에 overlap을 허용치 않는다. PML-tree의 performance는 여러 type의 test data(VLSI layout data, Tiger/Line, randomly distributed data)를 사용하여 MXR-tree와 비교된다. PML-tree는 MXR-tree에 비해 높은 공간활용도와 빠른 query response를 보임으로써 공간 database를 위한 효율적인 index structure로 사용이 될 것으로 기대된다.

목차 (Table of Contents)

• Ⅰ. 서 론
• Ⅱ. PML-tree
• Ⅲ. Performance 비교
• Ⅳ. 결 론
• 참고문헌