04-12-2012, 06:41 PM
Incremental and General Evaluation of Reverse Nearest Neighbors
Incremental and General.pdf (Size: 1.07 MB / Downloads: 21)
Abstract
This paper presents a novel algorithm for Incremental and General Evaluation of continuous Reverse Nearest
neighbor queries (IGERN, for short). The IGERN algorithm is general in that it is applicable for both continuous
monochromatic and bichromatic reverse nearest neighbor queries. This problem is faced in a number of applications
such as enhanced 911 services and in army strategic planning. A main challenge in these problems is to maintain the
most up to date query answers as the dataset frequently changes over time. Previous algorithms for monochromatic
continuous reverse nearest neighbor queries rely mainly on monitoring at the worst case of six pie regions, whereas
IGERN takes a radical approach by monitoring only a single region around the query object. The IGERN algorithm
clearly outperforms the state-of-the-art algorithms in monochromatic queries. We also propose a new optimization
for the monochromatic IGERN to reduce the number of nearest neighbor searches. Furthermore, a filter and refine
approach for IGERN (FR-IGERN) is proposed for the continuous evaluation of bichromatic reverse nearest neighbor
queries which is an optimized version of our previous approach. The computational complexity of IGERN and FRIGERN
is presented in comparison to the state-of-the-art algorithms in the monochromatic and bichromatic cases. In
addition, the correctness of IGERN and FR-IGERN in both the monochromatic and bichromatic cases respectively
are proved. Extensive experimental analysis using synthetic and real datasets shows that IGERN and FR-IGERN is
efficient, is scalable, and outperforms previous techniques for continuous reverse nearest neighbor queries.
INTRODUCTION
THE past decade has seen the assimilation of sensor networks and location-based systems in real world
applications such as enhanced 911 services, army strategic planning, retail services, and mixed-reality games.
The continuous1 movement of data objects within these applications calls for new query processing techniques that
scale up with the high rates of location updates. While numerous works have addressed continuous range queries
(e.g., see [1], [2], [4], [6], [7]) and continuous nearest neighbor queries (e.g., see [3], [5], [8], [9], [11]), there is
still a lack of research in addressing the continuous reverse nearest neighbor queries.
There are two types continuous evaluation of Reverse Nearest Neighbor (RNN) queries, namely, monochromatic
RNN and bichromatic RNN [12]. In the monochromatic RNN, all moving data and query objects are of the same
type and their locations are reported at every time interval t. Thus, a data object o is considered a reverse nearest
neighbor to a query object q if there does not exist another data object o! where dist(o, o!) < dist(o, q) and the
answer is updated at every t. Applications of the continuous monochromatic RNN include mixed reality games
(e.g., Botfighters) where the objective is to shoot only those players that are nearest to you. Thus, each player
should monitor his own reverse nearest neighbors to avoid being shot.
RELATED WORK
There is a recent interest in developing new continuous query processors to cope with the recent advances in
dynamic location-aware environments [22], [23]. As a result, new algorithms have been developed for various
types of continuous location-based queries, e.g., continuous range queries [1], [2], [4], [6], [7], continuous nearest
neighbor queries [3], [5], [8], [9], [11], and continuous aggregates [24], [25]. Although reverse nearest neighbor
queries are of the same importance as these query types, little work has been done to develop efficient algorithms
for continuous reverse nearest neighbor queries.
CONTINUOUS EVALUATION OF MONOCHROMATIC REVERSE NEAREST NEIGHBORS
This section presents the IGERN algorithm for monochromatic reverse nearest neighbor queries. The IGERN
algorithm maintains a grid data structure G of N × N equal size cells. Each cell c " G keeps track of the set of
objects that lie within the cell boundary. In general, the IGERN algorithm has two main steps, namely, the initial
and incremental steps. The initial step is executed only once at the query issuing time T0, while the incremental
step is triggered at each time unit for all time intervals T throughout the life time of the continuous query. The
main idea is that the initial step reports the first query answer along with a bounded region and a set of objects to
be monitored within the incremental step. Then, the incremental step continuously updates the query answer while
changing the monitored region and the monitored set of objects. The initial and incremental steps are described in
Sections III-A and III-B, respectively, while Section III-D gives a general discussion of IGERN.
Design Decisions
A significant computational cost within the monochromatic IGERN method occurs within the verification step
in the incremental method (Line 10 of Algorithm 2). After each time interval, each of the RNN answers found in
the previous time interval must be verified by performing a NN search. To reduce the number of NN searches at
every time interval, we propose an optimization to Algorithm 2 to monitor the region around each RNN answer
with a radius of the distance to the query object. This optimization only applies to the scenario when the RNN
answer r and the query object q do not move to a new location at the next immediate time interval. In all other
scenarios (i.e., objects r and/or q moves to a new location), the original verification phase (Line 10 of Algorithm 2)
will be performed. If both r and q do not move to a new location and an object o enters the monitoring region
of r, then r is no longer a RNN of q and no NN search needs to be performed. Otherwise, if an object does not
move into the monitoring region of r, then r remains to be a RNN for q and no NN search needs to be performed
to verify r. Unlike traditional continuous NN approaches where the monitoring region shrinks when an object
enters the monitoring region, this optimization removes the monitoring region when r is no longer a RNN. Only a
monitoring region is kept for RNN answers for q. Experimental evaluation shows that when objects do not move
as often at every time interval, a significant savings may occur for the proposed optimization (Section VII-C.1 and
Section VII-D.1).
ANALYTICAL COMPARISON OF RNN ALGORITHMS
This section presents the cost model for three monochromatic and two bichromatic algorithms. Namely for the
monochromatic case, we present the cost model for IGERN, CRNN [10], and repetitive evaluation of the static
TPL algorithm [17]. For the bichromatic case, we present the cost model for IGERN [21], the refined Filter and
Refine FR-IGERN approach, and the repetitive computations of the static creation of Voronoi cells [32]. Finally,
we compare the cost model of IGERN with its counterparts for both the monochromatic and bichromatic cases.
For each cost model, the total time T is used to determine the entire costs of the methods for the complete
duration. In general, the sampling rate of a ‘middleware’ system may change due to the speed of the object. Since
our methods sit on top of this architecture, the total number of samples is accounted for within our cost models.
The details of this middleware architecture are beyond the scope of this paper.
CONCLUSIONS
In this paper, we have presented a novel algorithm for Incremental and General Evaluation of continuous Reverse
Nearest neighbor queries (IGERN, for short). IGERN is general in that it provides a unified framework for both
monochromatic and bichromatic reverse nearest neighbors. In addition, IGERN is incremental as it limits the
attention to only a single bounded region and a small set of moving objects rather than focusing on the whole
space. IGERN clearly shows enhanced performance over the state-of-the-art algorithms in continuous monchromatic
reverse neighbor queries. We also propose a new optimization for the monochromatic IGERN to reduce the
number of nearest neighbor searches in the validation phase which shows significant improvement over the IGERN
approach. Furthermore, our previous IGERN is the first algorithm that deals with continuous bichromatic reverse
nearest neighbors. An improved bichromatic FR-IGERN approach is proposed here using filter and refine steps.
The correctness of both the monochromatic and bichromatic FR-IGERN is proved by showing that IGERN is
accurate, i.e., any object returned by IGERN is a reverse nearest neighbor, and is complete, i.e., IGERN returns all
reverse nearest neighbors. Analytical comparison of IGERN with previous approaches for reverse nearest neighbors
is provided. Experimental evidence that supports the analytical comparison is given where IGERN outperforms
previous approaches for both monochromatic and bichromatic reverse nearest neighbor queries.