A Pruning Based Continuous RkNN Query Algorithm for Large k

Reverse k-nearest neighbor (RkNN) query is a hot-spot in spatio-temporal database. With the developing of mobile devices, continuous RkNN query becomes more and more important. Most of the previous methods use the two-step (filter-refinement) processing. However, for large k, the amount of calculation becomes very heavy, especially in the filter step. This is not acceptable for most mobile devices. This paper presents a novel algorithm for continuous RkNN queries based on pruning heuristics. The experiments show that the processing time of our method is still acceptable for most mobile devices when k is large.