그리드 기반의 질의 색인을 통한 효율적인 연속 영역 질의 처리 = An Efficient Continuous Range Query Processing Through Grid based Query Indexing

국문 초록 (Abstract)

본 논문에서는 기존 그리드 기반의 질의 색인 기법을 변형하여 보다 적은 저장 공간을 사용하면서 보다 빠른 연산을 수행하는 연속 영역 질의 처리 기법을 제안한다. 제안하는 기법의 주요 특징은 두 가지 이다. 첫째, 각 질의에 비트 식별자를 부여하고 그리드의 각 셀은 이러한 비트 식별자의 조합으로 이루어진 비트 열을 이용하여 질의들의 겹침 정보를 반영한다. 이러한 비트 열을 통해 셀이 어떤 질의들에 포함되어져 있는지 빠르게 판단한 수 있으며, 두 셀 사이의 각 셀을 포함하는 질의 식별자들을 비교하지 않고 비트 열만을 비교하여 질의들의 포함관계를 알아내어 불필요한 연산을 줄일 수 있다. 둘째, 셀들을 그룹단위로 관리하여 불필요하게 비트 열의 길이가 증가하여 저장 공간을 낭비하고 비트 열의 비교 연산 시간이 증가하는 문제를 해결한다. 제안하는 기법이 기존 연속 영역 질의 처리 기법에 비해 우수함을 성능 평가를 통해 입증한다.

다국어 초록 (Multilingual Abstract)

In this paper, we propose an efficient continuous range query processing scheme using a modified grid based query indexing to reduce storage spaces and to accelerate processing time. The proposed method has two major features. First, each query has a bit identifier and each cell in a grid has a bit pattern that consists of the bit identifiers of the queries. The bit patterns present the relationship between cells and queries. Using the bit patterns, we can compute quickly what queries overlap a cell in a grid and reduce the number of unnecessary operations by comparing the bit patterns without comparing the query identifiers when we compute the relation between cells and queries. Second, the management of cells in the grid by groups prevents from wasting the storage space through the increase of the length of the bit pattern and increasing the comparison costs of bit patterns. We show through the performance evaluation that the proposed method outperforms the existing methods.

참고문헌 (Reference)

• 1 "cGridex: Efficient Processing of Continuous Range Queries over Moving Objects" 345-356, 2005
• 2 "SINA: Scalable Incremental Processing of Continuous Queries in Spatio- temporal Databases" 623-634, 2004
• 3 S. Prabhakar, "Query Indexing and Velocity Constrained Indexing : Scalable Techniques for Continuous Queries on Moving Objects" 51 (51): 1124-1140, 2002
• 4 K. L. Wu, "Processing continual range queries over moving objects using VCR-based query indexes" 226-235, 2004
• 5 G. Kollios, "On indexing mobile objects" 261-272, 1999
• 6 K. L. Wu, "On Incremental Processing of Continual Range Queries for Location-Aware Services and Applications" 261-269, 2005
• 7 D. Pfoser, "Novel approaches to the indexing of moving object trajectories" 395-406, 2000
• 8 "Motion adaptive indexing for moving continual queries over moving objects" 427-436, 2004
• 9 D. V. Kalashnikov, "Main Memory Evaluation of Monitoring Queries Over Moving Objects" 15 (15): 117-135, 2004
• 10 S. Saltenis, "Indexing the positions of continuously moving objects" 331-342, 2000
• 11 P. K. Agarwal, "Indexing moving objects" 175-186, 2000
• 12 Y. Cai, "An Adaptive Query Management Technique for Real-time Monitoring of Spatial Regions in Mobile Database Systems" 259-266, 2002