R-tree 계열의 인덱싱 구조에서의 효율적 질의 처리를 위한 VP 필터링

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 29권 / 6호 / 453 ~ 463페이지
· 저자명 : 김병곤, 이재호, 임해철

초록

정보사회가 인터넷의 보급과 더불어 복잡해짐에 따라 데이타베이스의 흐름은 문자나 숫자와 같은 일차원적인 데이타가 아닌 지리정보, 멀티미디어 데이타와 같은 다차원의 데이타를 저장하고 이에 대한 질의를 처리할 수 있는 시스템을 요구하고 있다. 따라서, 다차원적인 특성을 지니는 데이타에 대한 효율적 검색을 위한 다차원 인덱싱 구조에 대한 연구가 활발히 진행되어 왔으며, 그와 동시에 이러한 인덱싱 구조하에서 효율적인 질의 처리를 위한 연구도 병행되고 있다. 다차원 데이타는 그 다양한 응용분야에 따라 요구되는 질의의 형태가 각각 다르므로 이에 대응할 수 있는 알고리즘의 연구가 필요하다. 현재, 많은 다차원 데이타 처리 시스템이 R-트리계열의 인덱싱구조를 근간으로 구성되었으나, 현재까지의 질의처리 기법은 질의처리시에 필터링 특성을 지니지 않으므로, 객체들간의 다차원 거리계산으로 인하여 많은 질의처리시간을 소요한다.본 논문에서는 다차원 데이타를 처리하기 위한 R-트리 계열의 다차원 인덱싱 구조에서의 효율적인 질의처리를 위하여 질의처리 대상 객체를 줄이기 위한 필터링 기법을 소개하였다. 필터링을 수행하기 위하여 VP-트리와 MVP-트리에서 사용되었던 VP(Vantage Point)를 이용한다. 먼저, VP 필터링의 개념을 소개하고, VP 필터링을 영역질의와 포인트 질의의 일종인 추가객체요구질의에 각각 적용한 알고리즘을 제시하였다. VP 필터링을 적용하기 위하여 요구되는 삽입 객체와 VP간의 거리계산 시간은 객체의 삽입시 수행되며, 질의 처리를 수행할 때에는 다시 계산되지 않는다. 논문에서는 제안된 알고리즘의 효율성을 실험을 통하여 증명하였다.

참고자료

· 없음