도로 네트워크 데이터베이스를 위한 근사 인덱싱

Abstract

최근, LBS의 수요가 증가함에 따라 도로 네트워크 데이터베이스에서 효과적인 질의 처리 방안이 활발히 논의 되고 있다. 본 논문에서는 도로 네트워크 데이터베이스 분야에서 최근 널리 사용되고 있는 k-최근접 이웃 질의를 대상으로 한다. k-최근접 이웃 질의 처리 시 성능 저하라는 문제와 저장 공간의 큰 오버헤드라는 문제점을 동시에 해결하기 위하여 정적 객체들 간의 네트워크 거리를 기반으로 근사 인덱싱하는 새로운 기법을 제안하였다. 제안한 기법은 정적 객체 인덱스를 구축하기 위하여 도로 네트워크 위의 모든 정적 객체를 m차원 유클리드 공간상의 절대 위치로 매핑시킨다. 이 때 절대 위치 설정 기준은 m차원 유클리드 공간상의 임의의 두 정적 객체간의 거리가 실제 네트워크 거리를 가능한 유지하도록 하는 것이다. 이후 정적 객체의 매핑된 위치를 다차원 공간 인덱스인 R-트리를 이용하여 인덱싱한다. 질의 처리 시 질의 점 역시 다른 모든 정적 객체와의 네트워크 거리를 가능한 유지하도록 m차원 유클리드 공간상의 한 점으로 매핑시킨다. m차원 유클리드 공간상의 질의 점을 이용하여 정적 객체 인덱스를 탐색함으로서 k-최근접 이웃 질의를 빠르게 처리할 수 있다. 또한 제안하는 기법은 k-최근접 이웃 질의뿐만 아니라 영역 질의, 공간 조인 등 다양한 질의들도 효과적으로 처리할 수 있다. 제안된 기법의 우수성을 입증하기 위해 다양한 실험을 통하여 정확도 및 성능 비교 실험을 수행하였다. 실험 결과, 제안한 방식은 평균 94%의 응답도와 84%의 정밀도를 보이는 것으로 나타났다. 질의 처리 성능 은 매개 변수의 대표 값일 때 기존 INE와 비교하여 20배의 성능 향상을 보였다.; Recently, according to increase of demands for LBS, numerous methods for efficiently query processing have been discussed in road network databases. In this paper target query is the k-nearest neighbor queries which is widely used recently from spatial databases. In road network databases past researches have either performance overhead or storage overhead to processing k-nearest neighbor queries. To solve the problems we propose an approximate indexing method based on network distance. This method maps static objects and query points in road network to points in Eucildean space of m-dimension with network distance and indexes the mapped points. Then k-nearest neighbor query processing can be performed rapidly using the index. this method can be used not only k-nearest neighbor queries but also other query types(e.g., range queries, spatial join queries etc.). For accuracy verification and performance evaluation, we conduct a variety of experiments. The result of experiments for accuracy verification show that our method appears recall of average 94% and precision of average 84%. And the result of experiments for performance evaluation show that our method improves the performance in processing k-nearest neighbor queries by up to 20 times, compared with the INE method.