고정 그리드 인덱싱에서 공간과 시간 필터링을 이용한 범위 질의 처리
Range Query Processing using Space and Time Filtering in Fixed Grid Indexing
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
최근 들어 이동 통신 분야에서 이동하는 고객을 위한 위치 기반 서비스가 중요한 서비스로 부각되고 있다. 이동객체 응용의 경우 갱신 연산이 많고, 부하가 특정 지역에 집중되는 특징이 있다. 윈도우 나 원형 형태의 범위질의는 위치 기반 서비스에서 중요한 질의 중 하나이다. 이러한 범위질의에서는 부분 포함된 셀과 완전 포함된 셀을 구분해야할 필요가 있다. 또한 올바른 한정된 객체를 골라내기 위해 시간 영역을 고려할 필요성이 있다. 본 논문에서는 갱신연산을 최소화하기 위해 고안되어진 2번째 단계에 고정 그리드 구조를 적용한 2단계 인덱스 구조를 적용한다. VP 필터링과 윈도우 셀 필터링 기법을 이용한 공간 셀 필터링 기법과 Time Zone 개념을 사용하여 시공간 개념이 결합된 필터링 기법을 제안한다. 제안된 방법의 성능 측정을 위해서 다른 필터링 조합을 가지고 다양한 윈도우 질의와 원 질의에 대해서 실험 결과를 보인다.
Abstract
Recently, the location-based service for moving customers is becoming one of the most important service in mobile communication area. For moving object applications, there are lots of update operations and such update loads are concentrated on some particular area unevenly. Range queries, whose range can be window or circular, are the most essential query types in LBS. We need to distinguish completely contained cells from partially contained cells in those range queries. Also, it is necessary to consider temporal dimension to filter out qualifying objects correctly. In this paper, we adopt two-level index structures with fixed grid file structures in the second level, which are designed to minimize update operations. We propose a spatial cell filtering method using VP filtering and a combined spatio-temporal filtering method using time zone concepts. Some experimental results are shown for various window queries and circular queries with different filtering combinations to show the performance tradeoffs of the proposed methods.
참고문헌 (17)
- "J.A.Orenstein and T.H. Merrett. A class of data structures for associative searching Proc. of SIGACT-SIGMOD"
- "대용량 이동 객체의 위치 정보 인덱싱", 29(2), pp.49~51 (2002)
- "고정그리드 인덱싱에서 VP 필터링을 이용한 범위 질의 처리", 제10권(제1호), pp.pp.1531-~1534 (2003)
- "TMO-structured Cluster-based Real-Time Management of Location Data on Massive Volume of Moving Items" (2003)
- "Distributed Adaptive Architecture for Managing Very Large Volume of Moving Itemsidpt 2003" (2003)
- "LBS 시스템의 클러스터 기반 신축성소유 아키텍처 데이터베이스연구", 제18권(제4호), pp.33~47 (2002)
- "Indexing the Positions of Continuously Moving Objects" (2000)
- "Spatio- Temporal Indexing for Large Multimedia Applications" (1996)
- "RT-tree：An Improved R- tree Index Structure for Spatiotemporal Databases Proc. 4th Int’l Symp. on Spatial Data Handling" (1990)
- "Satisfying General Proximity", Similarity Queries with Metric Trees, 1991., pp.40, 175~179
- "Distance-Based Indexing for High-Dimensional Metric Spaces", pp.357~368 (1997)
- "Data Structures and Algorithms for Nearest Neighbor search in General Metric Spaces", pp.311~321 (1993)
- "R-tree 계열의 인덱싱 구조에서의 효율적 질의 처리를 위한 VP 필터링", 29(6), pp.453~463 (2002)
- "Spatial Databases with Application to GIS", Morgan Kaufmann.
- "Time-Parameterized Queries in Spatio-Temporal Databases" (2002)
- "Continuous Queries over Append-only Databases" (1992)
- "NiagaraCQ：A Scalable Continuous Query System for Internet Databases" (2000)