Threaded Quadtree : 이웃 검색을 위한 효율적인 색인 구조

조대수, 최진오, 홍봉희 · 한국정보과학회 학술발표논문집 · 1996

대용량의 데이타를 처리해야 하는 GIS는 사용자로부터의 공간 질의를 효율적으로 수행하기 위하여 공간 색인을 사용하고 있다. 기본 테이블의 공간 관련성을 기반으로 한 위상 연산이 필요한 질의를 추가의 위상 정보 없이 공간 색인만을 이용하여 처리하기 위해서는 공간 색인에 대해 위상 연산을 수행하기 위한 알고리즘이 필요하다. 이 논문에서는 quadtree를 공간 색인으로 사용할 때, 위상 연산을 수행하는데 기본이 되는 서로 인접한 노드의 검색을 효율적으로 처리하고자 한다. 이를 위하여 기존의 quadtree를 변형하지 않고, 대신에 말단 노드에서 사용하지 않고 있는 네 개의 NULL 포인터를 자신의 이웃을 가리키는 쓰레드로 사용하는 threaded quadtree를 제시하고, threaded quadtree의 분할, 병합시에 쓰레드를 관리하는 방법을 제시한다. 그리고 이를 이용하여 자신의 이웃을 효율적으로 검색하는 방법을 제시한다. 따라서 이 논문에서 제시하는 방법은 기존 quadtree에서 사용되던 모든 연산을 그대로 사용할 수 있으며, 추가적인 저장 장소의 낭비 없이 효율적으로 이웃 노드를 검색할 수 있는 장점일 가지고 있다.

Cited by 0 works.

Authors