Conclusion

In this chapter, we present techniques for several variants of $k$ nearest neighbor queries. We believe that CircularTrip and ArcTrip can be used to continuously monitor many other variants of nearest neighbor queries (e.g., nearest surrounder queries [LLL06] and aggregate nearest neighbor queries). Though CPM can be used to answer some of these queries but it is not efficient because CPM was designed only for $k$ nearest neighbor queries. Our CircularTrip-based algorithm performs 2 to 4 times better than CPM even for $k$ NN queries and it is easy to verify that for the variants presented in this chapter, our presented approaches are still optimal in accessing the number of cells. Hence the performance of our approaches is expected to be much faster than all previous approaches.

Moreover, it is easy to see that our approach can answer any query that is a hybrid of above mentioned queries. For example, we can use ArcTrip to continuously monitor ($k+m$ ) farthest neighbors in a Donut-Pie constrained region where the constraints that define the region may be changed by the user at any time. For all these queries, our proposed algorithms visit minimum number of cells.