R-tree에서 위치 기반 질의를 지원하기 위한 동적 셀 레벨링 = Dynamic Cell Leveling to Support Location Based Queries in R-trees

다국어 초록 (Multilingual Abstract)

Location Based Services(LBSs) in mobile environments become very popular recently. For efficient LBSs, spatial database management systems must need an spatial indexing scheme such as R-trees in order to manage the huge spatial database. However, it may need unnecessary disk accesses since it needs to access objects which are not actually concerned to user's location-based queries. In this paper, to support the location-based queries efficiently, we propose a CLR-tree(Cell Leveling R-tree) in which a dynamic cell is built up within the minimum bounding rectangle of R-trees' node. The cell level of nodes is compared with the query's cell level in location-based query processing and determines the minimum search space. Also, we propose the insertion, split, deletion, and search algorithms for CRL-trees. From the experimental results, we see that a CLR-tree is able to decrease 5～20% of disk accesses from those of R-trees. So, a CLR-tree can be used for fast accessing spatial objects to user's location-based queries in LBSs.

국문 초록 (Abstract)

최근 GPS기능을 탑재한 휴대폰PDA등의 모바일 장치를 사용하여 위치 기반 서비스를 이용하는 사용자가 급증하고 있다. 이에 위치 정보를 지닌 공간 데이타를 저장하고 관리하는 대용량의 공간 데이타베이스는 사용자의 다양한 질의 조건과 빠른 검색을 가능하게 하기 위한 색인이 필요하며 대표적인 색인 기법으로는 R-tree가 널리 사용되고 있다. 기존의 R-tree를 이용한 검색은 질의 영역과 관계없는 공간 데이타까지 검색하여 불필요한 입출력을 유발하기 때문에 응답시간이 늦어진다. 본 논문에서는 공간 데이타가 위치 기반 질의를 지원하기 위해 자신이 속한 노드의 전체(Union) MBR 영역에 따라 동적으로 셀 레벨 값을 구성하는 CLR-트리(Cell Leveling R-tree)를 제안한다. 또한, CLR-트리에서의 새로운 공간 데이타의 삽입, 분할, 삭제, 검색 알고리즘을 제안한다. 제안된 CLR-트리에서는 위치 기반 질의 시 사용자 질의 영역의 셀 레벨 값과 공간 데이타의 셀 레벨 값을 비교하여, 겹치지 않는 셀에 대해서는 검색 대상으로부터 제거하고 연관된 셀만을 검색하기 때문에 빠른 응답시간을 제공함을 알 수 있다. 디스크 입출력 실험에서 CLR-트리가 기존 R-tree보다 디스크 접근 수를 5～20% 감소시켜 사용자의 위치 기반 질의에 대해 빠르게 처리함을 알 수 있었다.

참고문헌 (Reference)

1 "이동체의 색인을 위한 시간 기반 R-트리의 설계 및 구현" Vol.30 (Vol.30): 320-335, 2004.

2 "The X-Treean index structure for high dimensional data" 1996.

3 "The R+-Tree:A Dynamic index for multi-dimensional objects" 1987.

4 "The R*-tree:An Efficient and Robust Access Method for Points and Rectangles" 322-331, 1990.

5 "Spatial access to multidimensional point and non-point objects Proceedings of the 15th International Conference on VLDB" 45-53, 1989.

6 "Spatial Query Processing in an Object-Oriented Database System" 326-336, 1986.

7 "Proceedings of the Information and Knowledge Management" 490-499, 19941994.

8 "Multi-step Processing of Spatial Joins" 197-208, 1994.

9 "Location dependent data and its management in mobile databases" 414--419, 1998.

10 "An effective way to represent quadtrees Communications of ACM" 25 : 905-910, 1982.

11 "An Introduction to Spatial Database System" 3 no. 4 : 357-399, 1994.

12 "An Dynamic Index Structure for Spatial Searching Proceedings of the ACM SIGMOD" 47-57, 1984.

13 "An Architecture for Location Dependent Query Processing" 2001.

14 "A new representation of polygonal objects supporting spatial queries and operations Proceedings of the 7th Workshop on computational Geometry Lecture Notes in Computer Science 553" Springer-Verlag 249-264, 1991.