Continuous $k$ NN Queries

Different from a snapshot $k$ NN query, continuous $k$ NN queries are issued once and run continuously to generate results in real-time along with the updates of the underlying datasets. Since mobile devices are now able to detect their postions, the continuous monitoring of the spatial queries have become one of the most interesting problems in spatio-temporal databases. Objects send their location updates and the results of queries are updated accordingly.

The problem of continuously monitoring $k$ NN of moving objects has been investigated largely in past few years. From the modeling and query language perspectives, continuous monitoring of $k$ NN queries was first addressed in [SWCD97]. Kollios et al. [KGT99] were first to consider answering $k$ NN queries for moving objects in 1D space. Song et al. [SR01] presented the first algorithm for computation of a moving $k$ NN query $q$ over static data set in high dimensional space. Server sends to client a number $m>k$ of neighbors when a $k$ NN query is processed. The $k$ nearest neighbors at a new location $q'$ will be among the $m$ objects of the first query $q$ provided that the distance between $q$ and $q'$ is within a range determined by $k$ and $m$ . For the same setting where queries are moving and data set is static, Zhang et al. [ZZP$^+$03] proposed a solution that returns the NN of query $q$ along with its Voronoi cell, where Voronoi cell is the area in which the NN of query will remain same.

Assuming that the velocity of linearly moving data objects is known, time-parameterized queries [TP02] report the current NN set and its validity period and the next change of the result that will occur at the end of the validity period. Such queries use TPR-tree [SJLL00] or its variants such as TPR*-tree [TPS03](extension of R*-tree by augmenting the indexed objects and the MBRs with the velocity vectors). In [BJKS02], authors propose a solution by depth-first traversal of TPR-tree. Their approach returns all NN sets up to a future time assuming that the velocity vector of the query will not change up to that time. Raptopoulou et al. [RPM03] proposed a method by combining the merits of [TP02] and [BJKS02] which significantly reduces the I/O and CPU costs.

All of the above methods and [ISS03] work only when the future trajectories of objects are known at query time by either some linear function or some recursive function [TFPL04]. As discussed in Section , most widely used approach to answer conventional snapshot $k$ NN queries is using R-tree index. R-tree index cannot be used for efficiently monitoring of $k$ NN queries because it cannot support frequent updates of data objects. Though a bottom-up update approach of updating R-tree was introduced in [LHJ$^+$03], recently the interest of database community has been shifted towards using grid-based index to answer continuous $k$ NN queries over highly dynamic data sets. Since grid-based index is simple, it can be easily updated with the updates of data point location updates. Kalashnikov et al. [KPH04] used the in-memory grid structure to monitor continuous range queries. The most related and recent works [MHP05,XMA05,YPK05] all employ grid-based index. The space is partitioned into a regular grid of cells $\delta \times \delta$ and each algorithm computes the results of each query every $T$ time units. These algorithms do not make any assumption on the motion pattern of data points and/or query points. Since these are the most recent, most related and the best known algorithms, we briefly describe them below.