Technique

We presented ArcTrip in chapter  and now we discuss how ArcTrip can be used to efficiently monitor continuous pie-region $k$ CNN queries. The continuous monitoring of a $k$ CNN query $q$ with angle range $\langle \theta_1,\theta_2 \rangle$ is similar to the continuous monitoring of NN queries described in chapter . The only difference is that we call ArcTrip( $q,r,\langle \theta_1,\theta_2\rangle$ ) instead of CircularTrip($q,r$ ) and for any object $p$ that lies outside the constrained region $dist(p,q)=\infty$ .

Below we describe the continuous monitoring of the pie-region $k$ CNN query assuming that initial results are known because the computation of initial results is trivial. Similar to monitoring of NN queries, the update modules handles the updates by categorising them as internal, incoming and outgoing updates. After handling all the updates, if $q.kNN$ contains more than or equal to $k$ objects, the result of query is updated by selecting the $k$ closest objects and deleting others. Otherwise if $q.kNN$ contains less than $k$ objects, ArcTrip with angle range $\langle \theta_1,\theta_2 \rangle$ and radius $q.dist_k$ is called and radius is incremented by $\delta$ everytime unless $k$ NNs are found.

Figure: A Continuous Pie-Region $1$ -CNN query

[$p_1$ issues an update at $p'_1$ ] [$p_2$ is new CNN]