25-04-2012, 05:05 PM
Continuous Monitoring of Distance-Based Range Queries
Continuous Monitoring of.pdf (Size: 1.81 MB / Downloads: 49)
INTRODUCTION
WE consider a set O of objects, a query point q, and a
positive value r. We use distðo; qÞ to denote the
distance between an object o 2 O and the query q. A
distance-based range query returns every object o 2 O that
lies within distance r of the query location q, i.e., every
object such that distðo; qÞ r. Our main focus in this paper
is on euclidean distance-based range queries. Since the
search space around the query is a circle in this case, such
queries are also called circular range queries. We also
consider the case when distðo; qÞ is the network distance
between o and q (e.g., queries moving in a road network).
RELATED WORK
Spatial Queries in Euclidean Space
Continuous monitoring of spatial queries has been extensively
studied in the recent past [9], [10], [2], [11], [3], [12],
[13], [6]. Prabhakar et al. [14] proposed velocity constrained
indexing and query indexing for continuous evaluation of
static queries over moving objects. Mokbel et al. [15]
introduced an algorithm (SINA) for evaluating a set of
concurrent spatial queries, which reduces the overall cost
by shared execution and incremental evaluation.
FRAMEWORK
Solution Overview
Consider the example in Fig. 3 where a range query q is
shown. Its range is r and the area within its range is shown
shaded. Some objects around it are also shown. The objects
that lie within the range form the result set and are called
internal objects (e.g., the objects o1 and o2). The objects that
do not lie within the range are called external objects (e.g.,
the object o3). Let Ci be a circle of radius r with center at the
location of the object oi. Fig. 3 shows the circles for the
objects o1, o2 and o3.
CONCLUSION
In this paper, we presented a safe zone-based approach to
efficiently monitor distance-based range queries in euclidean
space and in road networks. We conducted a rigorous
theoretical analysis to study the effectiveness of our safe
zone-based approach for euclidean distance-based range
queries. The experiment results also demonstrated that the
proposed approach for euclidean distance based-range
queries is close to optimal. We also showed that our
network distance-based algorithm is an order of magnitude
faster than a naı¨ve approach.