Abstract:With the rapid development of smart mobile devices and wireless location techniques, more and more users tend to attempt location-based service. Specifically, mobile users usually request continuous queries based on moving trajectories instead of traditional snap-shot queries for fixed locations. As obstacles can be found everywhere in the real-world or virtual space, more and more attentions has been paid on query processing techniques in the obstructed space. Notably, continuous reverse k-nearest neighbor queries in obstructed space are widely used. This paper presents an in-depth study on the problem of moving reverse k-nearest neighbor queries in obstructed spatial databases. By defining control points and split points, the processing framework for this problem is constructed. Furthermore, several pruning and verification algorithms, including data points reduction, obstacles retrieving, control points calculating and results set updating, are proposed to improve the query efficiency. Extensive experimental evaluation is conducted based on various datasets. Compared with the basic method which computes the k-nearest neighbors for each data point, the proposed methods can significantly improve CPU and I/O efficiency.