대용량 이동객체의 위치정보 관리를 위한 S-GRID를 이용한 분산 그리드 기법 = Distributed Grid Scheme using S-GRID for Location Information Management of a Large Number of Moving Objects

다국어 초록 (Multilingual Abstract)

Recently, advances in mobile devices and wireless communication technologies require research on various location-based services. As a result, many studies on processing k-nearest neighbor query, which is most im portant one in location-based services, have been done. Most of existing studies use pre-computation technique to improve retrieval performance by computing network distance between POIs and nodes beforehand in spatial networks. However, they have a drawback that they can not deal with effectively the update of POIs to be searched. In this paper, we propose a distributed grid scheme using S-GRID to overcome the disadvantage of the existing work as well as to manage the location information of a large number of moving objects in efficient way. In addition, we describe a k-nearest neighbor(k-NN) query processing algorithm for the proposed distributed grid scheme. Finally, we show the efficiency of our distributed grid scheme by making a performance comparison between the k-NN query processing algorithm of our scheme and that of S-GRID.

국문 초록 (Abstract)

최근 모바일 기기 및 무선 통신의 발달로 인하여 다양한 위치 기반 서비스에 대한 연구가 증대되고 있으며, 이러한 위치 기반 서비스의 대표적 질의인 k-최근접 질의를 효율적으로 처리하기 위한 연구가 활발히 수행되어 왔다. 기존 연구들은 질의 처리 성능의 향상을 위해, 공간 네트워크 상의 POI와 노드 사이의 거리를 미리 계산하는 pre-computation 기법을 사용한다. 그러나 이러한 pre-computation 기법들은 검색 대상이 되는 POI의 변경을 효과적으로 처리하지 못하는 단점을 갖는다. 본 논문에서는 기존 pre-computation 기법들의 단점을 극복하고, 대용량 이동객체의 위치정보를 효율적으로 관리하기 위하여 S-GRID를 이용한 분산 그리드 기법을 제안한다. 아울러 제안하는 분산 그리드 기법을 위한 k-최근접 질의 처리 알고리즘을 제시한다. 마지막으로, S-GRID 및 분산 그리드 기법의 k-최근접 질의처리 알고리즘의 성능 평가를 통해, 제안하는 기법의 우수성을 입증한다.

참고문헌 (Reference)

1 이호, "분산 이동 객체 데이터베이스를 위한 과거 위치 정보 관리" 8 (8): 91-107, 2006

2 M. Kolahdouzan, "Voronoi-based Nearest Neighbor Search for Spatial Network Databases" 840-851, 2004

3 X. Huang, "The Islands Approach to Nearest Neighbor Querying in Spatial Networks" 73-90, 2005

4 Y. Nha, "TMO-structured Cluster-based Real-time Management of Location Data on Massive Volume of Moving Items" 89-92, 2003

5 X. Huang, "S-GRID: A Versatile Approach to Efficient Query Processing in Spatial Networks" 93-111, 2007

6 D. Papadias, "Query Processing in Spatial Network Databases" 802-813, 2003

7 H. Hu, "Fast Nearest Neighbor Search on Road Networks" 186-203, 2006