Continuous k-Nearest Neighbour Strategies Using the mqrtree

In this paper, two strategies for processing a continuous k-nearest neighbor query for location-based services are proposed. Both use a spatial access method, the mqrtree, for locating a safe region. The mqrtree supports searching within the structure, so searches from the root are not required - a property which is exploited in the strategies. However, the proposed strategies will work with most spatial access methods. The strategies are evaluated and compared against a repeated nearest neighbor search. It is shown that both approaches achieve significant performance gains in reducing the number of times a new safe region must be identified, in both random and exponentially distributed points sets.