이동객체 데이터베이스에서 내용부합 범위 모니터링 질의 처리 = Evaluation of Content-Matched Range Monitoring Queries over Moving Objects

다국어 초록 (Multilingual Abstract)

A content-matched (CM) range monitoring query over moving objects continually retrieves the moving objects (i) whose non-spatial attribute values are matched to given non-spatial query values, and (ii) that are currently located within a given spatial query range. The majority of existing methods for a traditional spatial range monitoring query, which considers only objects’ current locations, cannot efficiently deal with such a query. In this paper, we propose a new query indexing structure, called the group-aware query region tree(GQR-tree) for efficient evaluation of CM range monitoring queries. The GQR-tree groups queries according to their non-spatial query values when being built on their spatial query ranges. The primary role of the GQR-tree is to leverage the computational capabilities of moving objects by pushing some tasks of CM range monitoring query evaluation to the moving objects and makes the server to efficiently cooperate with the moving objects in order to reduce the amount of location update stream from the moving objects. Through a series of comprehensive simulations, we verify the efficiency of the GQR-tree in terms of the wireless communication cost and the server workload which depend on the amount of location update stream from moving objects.

국문 초록 (Abstract)

이동객체 데이터베이스에서 내용부합 범위 모니터링 질의는 (i) 이동객체의 비공간 속성 값이 주어진 비공간 질의 값과 부합하고, (ii) 주어진 공간 질의 범위 안에 위치하고 있는 이동객체들을 지속적으로 검색한다. 객체의 위치만 고려하는 기존 공간 범위 모니터링 질의 기법은 이러한 질의를 다루는데 효율적이지 못하다. 본 논문에서는 내용부합 범위 모니터링 질의들을 효율적으로 처리하는 새로운 질의 색인 구조인 GQR-tree(Group-aware Query Region Tree)를 제안한다. GQR-tree는 공간 질의 범위를 기반으로 구축될 때 비공간 질의 값에 따라 질의를 그룹화한다. GQR-tree는 이동객체의 연산능력을 활용하여 서버와 효율적으로 협력함으로써 내용부합 모니터링 질의 처리 작업을 하여 위치 업데이트 스트림 양을 최소화하는데 사용된다. 시뮬레이션들을 통하여 위치 업데이트 스트림 양에 밀접한 상관관계를 가진 무선 통신비용과 서버작업량 면에서 GQR-tree의 효율성을 입증한다.

참고문헌 (Reference)

1 Y. Tao, "The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries" 2003

2 N. Roussopoulos, "The R+-tree: A Dynamic Index for Multi-Dimensional Objects" 1987

3 N. Beckmann, "The R*-tree: An Efficient and Robust Access Method for Points and Rectangles" 1990

4 M. Song, "Spatial indexing for massively update intensive applications" 203 : 1-23, 2012

5 J. M. Patel, "STRIPES: An Efficient Index for Predicted Trajectories" 2004

6 M.F. Mokbel, "SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases" 2004

7 Y. Cai, "Real-Time Processing of Range-Monitoring Queries in Heterogeneous Mobile Databases" 5 (5): 931-942, 2006

8 A. Guttman, "R-trees: A Dynamic Index Structure for Spatial Searching" 1984

9 C.S. Jensen, "Query and Update Efficient B+-Tree Based Indexing of Moving Objects" 2004

10 S. Prabhakar, "Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects" 51 (51): 1124-1140, 2002

11 H. Jung, "QR-tree: An Efficient and Scalable Method for Evaluation of Continuous Range Queries" 274 : 156-176, 2014

12 H. Jung, "Processing Generalized k-Nearest Neighbor Queries on a Wireless Broadcast Stream" 188 : 64-79, 2012

13 J. Broch, "Performance Comparison of Multi-HopWireless Ad Hoc Network Routing Protocols" 1998

14 H. Jung, "On Processing Location Based Top-k Queries in the Wireless Broadcasting System" 2010

15 K.L. Wu, "On Incremental Processing of Continual Range Queries for Location-Aware Services and Applications" 2005

16 B. Gedik, "Mobieyes: A Distributed Location Monitoring Service Using Moving Location Queries" 5 (5): 1384-1402, 2006

17 D.V. Kalashnkov, "Main Memory Evaluation of Monitoring Queries Over Moving Objects" 15 (15): 117-135, 2004

18 S. Saltenis, "Indexing the Positions of Continuously Moving Objects" 2000

19 K.L. Wu, "Efficient Processing of Continual Range Queries for Location-Aware Mobile Services" 4 (4): 435-448, 2005

20 K. Mouratidis, "Continuous Monitoring of Spatial Queries in Wireless Broadcast Environments" 8 (8): 1297-1311, 2009

21 M.A. Cheema, "Continuous Monitoring of Distance-Based Range Queries" 23 (23): 1182-1199, 2011

22 J.L. Huang, "A Proxy-Based Approach to Continuous Location-Based Spatial Queries in Mobile Environments" 25 (25): 260-273, 2013

23 F. Liu, "A Hybrid Communication Solution to Distributed Moving Query Monitoring Systems" 10 (10): 214-226, 2011

24 H. Hu, "A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects" 2005