Extension to Varying Donut-Region Continuous $k$ CNN Queries

To show the flexibility of our technique, in this section we present the approach to answer the continuous $k$ CNN queries where the distance bounds $d_U$ and $d_L$ can be changed by user at any time. Consider the running example of Fig. , where the lower bound is changed from $d'_L$ to $d_L$ . Below we present the technique to efficiently compute the nearest neighbor after such change in constraints.

Suppose the lower distance bound is changed from $d'_L$ to $d_L$ and upper bound is changed from $d'_U$ to $d_U$ . Let $q.dist_k$ be the distance of current $k^{th}$ NN from $q$ . To update the results, first we delete the objects from $q.kNN$ that do not lie in the new range. More specifically we delete every $p\in q.kNN$ where $dist(p,q)<d_L$ or $dist(p,q)>d_U$ . If $d_L<d'_L$ , the algorithm starts calling CircularTrip with radius $d_L$ and iteratively increases it by $\delta$ unless $k$ NNs are found or radius equals or exceeds $d'_L$ . If $k$ NNs are not found and the radius equals to $d'_L$ , the algorithm continues by calling CircularTrip with radius $q.dist_k$ unless $k$ NNs are found or the radius equals to $d_U$ . Note that, if radius equals to $d_U$ and $k$ NNs have not been found this means there are less than $k$ objects that lie in the constrained region. We illustrate our technique with following example.

Figure: A Varying Donut-Region Continuous $1$ -CNN query

[Lower bound changes from $d'_L$ to $d_L$ ] [$p_2$ is still the CNN]