The processing of a Continuous Reverse k-Nearest-Neighbor (CRkNN) query on moving objects can be divided into two sub tasks: continuous filter, and continuous refinement. The algorithms for the two tasks can be completely independent. Existing CRkNN solutions employ Continuous k-Nearest-Neighbor (CkNN) queries for both continuous filter and continuous refinement. We analyze the CkNN based solution and point out that when k>1 the refinement cost becomes the system bottleneck. We propose a new continuous refinement method called CRange-k. In CRange-k, we transform the continuous verification problem into a Continuous Range-k query, which is also defined in this paper, and process it efficiently. Experimental study shows that the CRkNN solution based on our CRange-k refinement method is more efficient and scalable than the state-of-the-art CRkNN solution.
Index Terms:
reverse k-nearest-neighbor query, moving objects
Citation:
Wei Wu, Fei Yang, Chee Yong Chan, Kian-Lee Tan, "Continuous Reverse k-Nearest-Neighbor Monitoring," mdm, pp.132-139, The Ninth International Conference on Mobile Data Management (mdm 2008), 2008