A Pruning Based Continuous RkNN Query Algorithm for Large k

作者：Wang Shengsheng; Chai Sheng^*; Lv Qiannan

来源：Chinese Journal of Electronics, 2012, 21(3): 523-527.

• Continuous reverse k-nearest Neighbor
• Spatial database
• Pruning heuristics

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.

• 出版日期2012-7
• 单位吉林大学