Conclusion

We presented two grid traversal methods named CircularTrip and ArcTrip that return the cells based on their proximty to the query point. CircularTrip returns all the cells around query point $q$ that intersect the circle with center at $q$ and radius $r$ . ArcTrip goes one step further and returns only the cells that intersect the circle of radius $r$ and lie within some specific angle range. We have shown that the access methods are efficient and flexible. More specifically, each access method computes the $mindist$ of $\mid C\mid$ number of cells where $\mid C\mid$ is the number of cells returned by the access method.

We show the effectiveness of our grid access methods by introducing an algorithm for continuous monitoring of $k$ NN queries. Our experimental results show that our CircularTrip-based algorithm is 2 to 4 times faster than CPM which is previously best known algorithm. We prove that our algorithm accesses minimum number of cells for any continuous $k$ nearest neighbor query. Moreover, our algorithm uses less memory space. Unlike CPM, CircularTrip-based algorithm does not need any book-keeping information and still achieves a better performance. The space usage of our algorithm is 50$\%$ to 85$\%$ of CPM's space requirements.

We also proposed algorithms for continuously monitoring other variants of $k$ NN queries like constrained nearest neighbor queries, farthest neighbor queries and $(k+m)$ -NN queries. All previous approaches fail to efficiently monitor such queries. Our algorithms are very flexible, efficient and can easily be integrated to answer more complex queries. For example, our proposed algorithms can be easily used to answer ($k+m$ ) farthest neighbors in a constrained region where the spatial conditions that constrain the region can be changed by the user at any time. Moreover, all of the presented algorithms preserve the basic properties of visiting minimum number of cells for each continuous query and no book-keeping information is required.