Constrained Nearest Neighbor Queries

A constrained nearest neighbor query (CNN) [FSAA01] is a nearest neighbor query that is constrained to a specific region. This type of queries is of interest to the users who wish to find the nearest neighbor in some constrained region and not in the whole space. We had discussed the previous work on constrained nearest neighbor queries in Section . In [FSAA01], authors propose different techniques to answer CNN queries but to the best of our knowledge there is no efficient algorithm available for continuously monitoring the CNN queries. Continuous $k$ CNN query can be defined as to monitor the $k$ nearest neighbors in a constrained region. The constrained region is bounded by certain spatial conditions. Below, we categorise continuous $k$ CNN queries based on the constraints that bound the region.

• Continuous Pie-Region $k$ CNN Queries: The continuous $k$ constrained nearest neighbors queries where the region is bounded by some angle range $\langle \theta_1,\theta_2 \rangle$ are called continuous Pie-Region $k$ CNN queries. Formally, it monitors the $k$ NNs among a set of objects $P'\subseteq P$ such that all objects in $P'$ lie within the specified angle range. We call it Pie-Region queries because the constrained region is a pie shaped region.

• Continuous Donut-Region $k$ CNN Queries: Donut-Region $k$ CNN queries are the continuous $k$ CNN queries where the region is constrained by distance bounds. Let $d_L$ and $d_U$ be the lower and upper distance bounds, respectively. Continuous Donut-Region $k$ CNN queries can be formally defined as monitoring the $k$ NNs among a set of objects $P'\subseteq P$ such that for all $p\in P'$ , $d_U\geq dist(p,q)\geq d_L$ .

• Continuous Donut-Pie $k$ CNN Queries: As apparent from the name, a Donut-Pie $k$ CNN query constrains the region by both the angle and distance bounds. Let $\langle \theta_1,\theta_2 \rangle$ be the angle range and $d_L$ and $d_U$ be the lower and upper distance bounds, respectively. Continuous Donut-Pie queries monitor the $k$ NNs among the set of objects $P'\subseteq P$ such that for all $p\in P'$ , $d_U\geq dist(p,q)\geq d_L$ and $p$ lies within the angle range $\langle \theta_1,\theta_2 \rangle$ . The region looks like a pie taken from a donut, so we name it Donut-Pie queries.

• Continuous $k$ CNN Queries over Irregular Region: Given an irregular region $R$ , such queries are to continuously monitor $k$ NNs among the data objects $P'\subseteq P$ that lie inside $R$ .

In this section we present techniques for continuous monitoring of these $k$ CNN queries. We also present the techniques where the spatial conditions that constrain the region can be changed by the user at any time and our approach visits minimum number of cells for all the updates. More specifically, we present our technique to answer continuous pie-region $k$ CNN queries in section , donut-region $k$ CNN queries in section , donut-pie $k$ CNN queries in section  and continuous monitoring of $k$ CNN queries over irregular shaped region is described in section . In section  we give the concluding remarks showing the superiority of our approach.