Continuous Donut-Region $k$ CNN Queries

In this section we present algorithm to continuously monitor a $k$ CNN query where the region of the query is constrained by distance from $q$ . Formally, such a query $q$ continuously monitors the nearest neighbors among a set of objects $P'\subseteq P$ such that for all $p\in P'$ , $d_U\geq dist(p,q)\geq d_L$ where $d_U$ and $d_L$ are the upper and lower bounds of distance, respectively. Let $C_U$ and $C_L$ be the circles centered at $q$ and with radii $d_U$ and $d_L$ , respectively. The constrained region is the donut shaped area $C_U - C_L$ shown shaded in Fig. .

Figure: A Donut-Region $k$ CNN Query

As opposed to simple NN queries where the result would have been $p_1$ , the result of such query is $p_2$ because $p_1$ does not satisfy the constraint. Such queries have many applications. For example a user might be interested in $k$ NNs that are not nearer to him than 10km and not farther than 20km. Below we present the continuous monitoring of such queries.