Continuous Monitoring of Distance-Based Range Queries
- 17 December 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 23 (8) , 1182-1199
Abstract
Given a positive value r, a distance-based range query returns the objects that lie within the distance r of the query location. In this paper, we focus on the distance-based range queries that continuously change their locations in a euclidean space. We present an efficient and effective monitoring technique based on the concept of a safe zone. The safe zone of a query is the area with a property that while the query remains inside it, the results of the query remain unchanged. Hence, the query does not need to be reevaluated unless it leaves the safe zone. Our contributions are as follows: 1) We propose a technique based on powerful pruning rules and a unique access order which efficiently computes the safe zone and minimizes the I/O cost. 2) We theoretically determine and experimentally verify the expected distance a query moves before leaving the safe zone and, for majority of queries, the expected number of guard objects. 3) Our experiments demonstrate that the proposed approach is close to optimal and is an order of magnitude faster than a naïve algorithm. 4) We also extend our technique to monitor the queries in a road network. Our algorithm is up to two order of magnitude faster than a naïve algorithm.Keywords
This publication has 39 references indexed in Scilit:
- Efficient Construction of Safe Regions for Moving kNN Queries over Dynamic Datasets2009
- Continuous range monitoring of mobile objects in road networksData & Knowledge Engineering, 2008
- Efficient proximity and separation detection among mobile targets for supporting location-based community servicesACM SIGMOBILE Mobile Computing and Communications Review, 2006
- Continuous Expansion: Efficient Processing of Continuous Range Monitoring in Mobile EnvironmentsLecture Notes in Computer Science, 2006
- Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases2004
- Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates2003
- Query Processing in Spatial Network Databases2003
- Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objectsIEEE Transactions on Computers, 2002
- Semantic Caching in Location-Dependent Query Processing2001
- K-Nearest Neighbor Search for Moving Query Point2001