객체 분할 그리드에 기반한 병렬 공간 조인 처리

Abstract

본 논문에서 우리는 완전 비공유 구조 상에서 좋은 응답시간을 보이는 객체 분할 그리드에 기반한 병렬 공간 조인을 제안한다. 제안하는 방식은 공간 릴레이션을 동일한 크기의 그리드들로 분할한 후 공간 객체들을 위치에 따라 해당하는 그리드들에 할당한다. 이전에 제안되었던 방식과 달리 여러 그리드에 걸친 공간 객체들은 중복되지 않고 분할된다. 분할된 부분들은 다시 작은 크기의 완전한 다각형으로 재구성되어 해당하는 그리드에 저장된다. 각 그리드는 관계형 해쉬 조인의 버켓과 같이 취급될 수 있으며 조인 시 특별한 인덱스가 필요하지 않다. 본 논문에서는 제안하는 방식을 R-tree를 사용한 병렬 공간 조인 방식 및 공간 해쉬 조인과 비교한다. TIGER/Line 중 버지니아 지방의 Fairfield 군의 데이타를 사용하여 실험을 수행하였다. 실험은 제안하는 방식이 이전에 제안된 다른 방식보다 좋은 성능을 나타냄을 보여주고 있다.