Continuous Reverse Nearest Neighbor Monitoring
Tian Xia and Donghui Zhang
Abstract
Continuous spatio-temporal queries have recently received increasing
attention due to the abundance of location-aware applications. This
paper addresses the Continuous Reverse Nearest Neighbor (CRNN)
Query. Given a set of objects O and a query set Q,
the CRNN query monitors the exact reverse nearest neighbors of
each query point, under the model that both the objects and the query
points may move unpredictably. Existing methods for the reverse
nearest neighbor (RNN) query either are static or assume a priori
knowledge of the trajectory information, and thus do not
apply. Related recent work on continuous range query and continuous
nearest neighbor query relies on the fact that a simple monitoring
region exists. Due to the unique features of the RNN problem, it
is non-trivial to even define a monitoring region for the CRNN query.
This paper defines the monitoring region for the CRNN query, discusses
how to perform initial computation, and then focuses on incremental
CRNN monitoring upon updates. The monitoring region according to one
query point consists of two types of regions. We argue that the two
types should be handled separately. In continuous monitoring, two
optimization techniques are proposed. Experimental results prove that
our proposed approach is both efficient and scalable.